It could be that the ReplState table on your 5.5 server is damaged, or that something else is wrong with one of the tables. If your disaster recovery involved running an eseutil /p, this could very easily be the result of that. In 5.5, we have no ReplState test to fix up any ReplState problems. On top of that, it's hard to even troubleshoot these problems on 5.5 since we don't have the tracing options that we have in 2000 and beyond.
The only likely solution is to get the data out of that store and start over with a clean store on that server. I'd suggest using Outlook to pull the folders down to a PST (note that when you drag and drop a top-level folder into a PST, it will automatically grab all the subfolders as long as you have permissions to them). Then copy the data up to either the 2003 server or a clean store on the 5.5 server.
Sorry I don't have a better solution for you, but there is probably no way to fix that 5.5 store to make it replicate again.