Warning: we're in the business of DNS hosting.
Please don't hold that against me as I respond.
Most of us believe it's very important to have at least two DNS servers on two separate networks.
Why? Because if your server goes down and your only DNS server is on the same server than anyone trying to send email to any domain on the server will have that email returned with a "no such domain" error, and anyone attempting to visit a website on the server will get a "no such domain" message.
If the local network becomes unreachable (you can talk about this not happening all you want; for two days ending only a few hours ago no one from Cogent's network could reach anything on Level 3's network, and vice versa. It can and does happen)...
and if both your nameservers are on the same network you'll have the same problem (see above).
But with working DNS... (two nameservers on different servers on different networks) mailservers will continue to try for up to four days... and site visitors will see "website unavailable" (which is much better than no such domain).
So... you make the decision. I know which decision I've made; we have multiple nameservers worldwide.
I don't know anything about DNSmadeeasy.com, so I looked at their website; beware those ultra low TTL settings they brag about; if you use them two things will happen...
1) a lot of ISPs (AOL for example) will ignore your TTL records and set arbitrarily lengths, usually at least 24 hours
2) a lot of network administrators will see you as misusing the Internet and some may block your servers completely.
We don't use anything under ten minutes, and that works well for us and for our clients.
Jeff