I'm surprised you're looking at dedicated servers, but aren't interested in reseller accounts (in my experience, the former is always much more expensive than the latter).
I'd recommend going down the reseller account route. I had one with web-fusion for a while, which worked well with countless additional POP3 accounts, set up easily through the control panel.
I've now moved all my hosting to a reseller account with Heart Internet. As a result, every domain can be accessed individually by the client, to add as many additional POP3 accounts, a good webmail for each POP3, email forwarding addresses, extra ftp accounts, MySQL servers, etc. as I want to allow them (up to an unlimited number!).
I'm not sure of what is 'more effort than it's worth' with this, as I find them incredibly easy to set up, as do my clients.