Linode has worked well for me in the past.

Also I'm currently running a medium size mail server on hetzner.de. A 500 member list is nothing compared to that server.
--
My blog http://etbe.coker.com.au
Sent from a Galaxy S3
Android phone with K-9 Mail.