I believe I had the same issue one time before and it was because an attribute that was trying to be accessed was deleted. Do you remember deleting any attributes from the system that might have been used as a placeholder in your outbound mail reminders? If you did, just add it back and it should clear it all up. We had this happen and it was a nightmare until I added the attribute back, restarted the mail services and the background services.
Hope this helps,
When you say "after restarting the service" which do you mean. From memory I have had this issue previously, and I believe I restarted both the Outbound mail service, and the Background service to resolve it.