You can get PGP through Phil Zimermmann's Web site (the father of PGP). The program comes with the PGP Mail plug-ins. I've used it with MS Outlook before and it's a pretty seamless integration.

http://www.philzimmermann.com/EN/sales/index.html

The problem with something like MailVault is that they store your private key on their servers. The biggest threat to the security of encryption is the security of your private key. How can you trust that this company is going to keep it secure? They'll have access to it, hackers and spies could get access to it, and possibly law enforcement.

If you are the only one with access to your key then you're in a much better position: anyone who wants to get access to your encrypted files would have to break both your key and your passphrase. If you use mailvault, all someone has to do is break into your account using a simple username/password combo, which is not particularly secure, then they'll have access to your private key. They may still have to break your passphrase (I'm assuming that MailVault doesn't store this for you).

Of course, it is probably easier to use a service like MailVault, but I'm not convinced that it's worth it for questionable security benefits. And you have no way of knowing how trustworthy these people are or what the "back end" of this thing looks like.

Finally, with MailVault you have no way of knowing if your security has been compromised. If you control your private key, you're in a much better position to know if it has been stolen.