Curious if anyone can recommend a good backup mx service with the ability to search, at least queued emails (at least header info).. I cant seem to find many, though I did find Rollernet.. was looking for a few others to pick from... We also are probably at a 3gb per 14 day sort of quota as well (500MB per day), which complicates things, at least when our server would be down, this is how much is coming in, counting spam (which gets filtered after it hits the server). Thanks in advance

Have you looked at Microsoft's exchange hosted services? I'm not sure about searching mail that is in queue, but i know come their new release (dec 13th) you can perform message traces/searces. http://www.microsoft.com/exchange/services/default.mspx

I should add that if you have an EA with SA, this service is included in the exchange enterprise CAL.