[throwaway270925]

Gandi.net offers mail with custom domain and unlimited aliases. You need to have your domain registered with them though.

[Semaphor]

I wouldn't consider them an option since they got bought and had extreme price rises.

[throwaway270925]

If you consider single digit €/m "extreme", sure ...