Why not just have someone else host your email? Even cheap shared hosts will probably give you more email accounts than you need.
Any host using CPanel should give you complete control over your DNS, but even if not you can always
run your own nameservers and set the MX records appropriately.
-- Terrel
p.s. I am not very familiar with PHPNuke, but why can't you run it on a shared host?