Even on Ubuntu Server it's very very easy to setup a mail server. Linode has guides, and there are others on the interwebs as well.
Just make sure to implement a regular backup regime.
In my experience IMAP to my own mail server is WAY faster than dealing with Gmail (even web interface).
The most conservative approach would be a co-located machine that you own (i.e. your physical property, so they probably need a warrant) or on a machine in your home.