Actually, what I would like to do, is have the website on one server and the MX records handled by another. -- "640K ought to be enough for anybody." -- Bill Gates, 1981
That is fine too. I have my name servers hosted in one place, and my website in another. Just make sure the 'new' name servers are set up to your liking before you go to your domain registrar and make the switch.