There are several ways around this problem. Some firms 'peer' - firm A hosts the records for firm B, and firm B hosts the records for firm A. There are also third party (i.e. for fee, not for free!) companies which provide this service. I'm currently using DNS Made Easy. DNS Made Easy provides you with primary and secondary domains, and can provide mail services for your domains. The price per year is quite modest. Worth a look of you want to set up your company's web site and don't want to host DNS as well (or if you just want a reliable secondary).