Please correct me if I'm wrong, but it sounds like you want to use this single server to host websites AND resolve domains. The problem that your service provider has is that they wan the name server separate from your hosting domain. The only way I know how to do this is to have two servers. One could be virtual, but you're going to need another IP. That means you would have to install something like OpenVZ on your system. If I am wrong, please provide more information.
As far as mail services, I don't know enough about them to recommend one over the other. I run Courier. I'm sure there are plenty of smart people reading this post who would be better qualified to reply to this question.
Last edited by darinpeterson; 1st April 2013 at 16:48.
Reason: To ask for more detail