Option 1.
The best option is to buy for $15 a year a TLD (aka, mycompany.com) for additional $10 a month you can get a space on a full normal hosted server 24/7. Total cost about $150 per year.
Almost all of the Hosting services provide you with all that is necessary for email.
Your set your own email
everyone@mycompany.com and you can give a nice email service. Some of these servers provide both Webmail & POP3 email.
If security is important you have to make sure that the email can be configured with SSH, if you have SSH you do not need VPN.
Firewall, backups etc. are usually part of the deal.
Option 2.
Run your own server.
Linux is a good choice. However if you don not know Linux you will have to do a lot of basic learning work.
The following link has a collection of links for one of the Linux software options.
Link:
Linux Router.
If you are already familiar with WinXP it is relatively an easy project...
There is numerous amount of freeware and inexpensive shareware software that you can try before you finalize your decision.
Example:
ArGoSoft Mail Server.
You can find a Tutorial to set you own server here:
DNS - Domain Name System.