Hello,
Note: It is strongly suggested that Microsoft Article Q224977 and Q182903 are read completely before resolving this issue. It is also advisable that only someone with good working knowledge of Microsoft Exchange run the Exchange utility applications.
ESEUTIL will bring the Information Store and Directory store or Directory Services to a consistent state.
As you have mentioned that after running the eseutil/mh you found that edb file is inconsistent, it is may be bacuse the databse was backed up in inconsistent state.
In backup exec there is no option to check the databse consisatancy for Exchange like in SQL.
So we suggest you to contact Microsoft before running the exchnage utilities.
NOTE : If we do not receive your reply within two business days, this post would be marked assumed answered and would be moved to answered questions pool.