If I understand correctly, you basically want to know if there's a service that will run your e-mail through many different anti-spam programs?
Many operate by using filters on the body of the message, not the server it's from. I don't know of any services that do that, but it wouldn't surprise me if there were some. At work, I run our newsletters through command-line SpamAssassin to make sure no one chose words that happen to be favored among spammers, and our newsletter vendor has a Spam Test tool that does the same sort of thing.
If you think it's specifically your server, and not message content, check your IP in a DNSBL lookup tool, like http://www.dnsbl.info/ or the like. I don't know specifically what Paypal uses for anti-spam. Another question -- are you running SPF on your domain?
More specific to your problem than to the technical side of things, don't they send you a confirmation e-mail when they receive your mail? Did you get that? Is it possible that your anti-spam is rejecting their mail? Just a few thoughts.
Oddly PayPal doesn't seems to send a confirmation email... I've check my spam folder and it's empty.
I am actually using Google Apps for my domain email. From what I know, I think some spam filter checks the email header and match the domain name with the originating server? So if they detect that it is a Gmail server but the domain name's not gmail.com they would reject it? (Please correct me if i'm wrong)