Exchange 5.5 Information Store will not start

See if this thread from EE seems like your issue.

https://www.experts-exchange.com/questions/21164446/store-exe-crash-log-id-7024-error-2147746063.html

First off is the System Attendant and Directory Services started?
These must be started before the Information Store service can be started.

What errors are in the application log when the service fails to start?

Do you have a good backup? If so when was it created? Is restoring from backup an option as opposed to the possibility of losing email?

MS Exchange Directory is started, the System Attendant is started,  and the MTA seems to be hung at starting.

The App event log shows "Unable to initialize the MS Exchange information store service.  Error 0X8004010f.

I haven't had the chance to check on the backup yet.

What happened to cause the IS not to start?
Did the server reboot? If so why?
Did the service stop without the server rebooting?
If so I would double-check your anti-virus product (if you have one installed on the server). Check to make sure that you have EXCLUDED the EXCHSRVR folder on ALL drives.

What is the full error in the App log. By this I mean what is the event id, etc.

The Veritas backup of the public folders stopped working, so the backup admin re-started the server.  At that point the services did not start at startup of the server.  There is no anti-virus product on this server.  I am getting the following error in the app log:

Source: MSExchangeIS
Event ID: 5000
Type: Error
Unable to initialize the Microsoft Exchange Information Store service.  Error 0x8004010f.

When something like this happens it is always better to restore from backup provided you have Circular Logging disabled.
If your backup is good, then all the logfiles that were generated after the backup will be played into the database (provided they all exist and have not been deleted).

Otherwise you will have to run ESEUTIL /P against the database. This can however result in a loss of data.

Whichever way you go make sure that you copy the existing databases to a secure location so that you can always get back to where you are now.

We have already tried that, and unfortuately it didn't work.  I even did a re-install of exchange, and as long as I used the default empty databases all services would start.  When i then restored the backup up databases, the services wouldn't come back up again, even after running eseutil /p.

What about restoring from a day before the backup you used?  If you reinstalled exchange did you verify that everything was the exact same as before? Org name, server name, etc?

Maybe, but considering it is a dead product, they won't support it.