You should als mention the country. Helps if you're a business and not just looking for the cheapest. And maybe get a all-in-one solution if you don't want to set up and maintain mail yourself.
hetzner.de uberspace.de all-inkl.com netcup.de inwx.de are some I use or used.