Another VPS user here. Linode and Digital Ocean offer great guides to get started. I've basically moved two domains off of the formerly free Google Apps accounts onto my own servers. Overall things have gone well. I like being able to set my own file attachment size limits. As others have said, a 'clean' IP seems quite important. I've had emails disappear into Google's spam filters despite working previously, as repo…
I turned on "sieve_extprograms" inside Dovecot, dropped gpgit.pl into the correct directory, and now I just add stuff like this to my .sieve file:
filter "gpgit" ["--encrypt-mode", "prefer-inline", "mike.cardwell@example.com"];