Good thing with Hurricane Electric's service is that they also provide slave DNS capability.

So you can run your own DNS master server and rely on HE for availability when your server is down or even give preference to the slave DNS, so your users can get the results quick.