How do I avoid Lame DNS or other issues when switching between 3rd party DNS servers?

I have 800 DNS zones at many different providers, and am trying to centralize them to either UltraDNS or Dynect.

Is is possible for me to configure each NS to nameserverX.MyCompany.com and avoid having to make 800 edits every time a new DNS server is added?

For example

 ---------------
 This value is in DNS
 Also this value is in  
  the Whois registry

 ns1.company.com      -->     usa.hosted.com
 ns2.company.com      -->     UK.hosted.com
 ns3.company.com      -->     otherhosted.com
 ns4.company.com      -->     secondary.netscaler.com
 ns5.company.com      -->     usa.hosted.com  <-- duplicate, for future use

IS the above configuration valid?

Should I use A or CNAME records?

Is there a chance this will cause DNS Lameness, or other issues?

You can certainly create a set of nameservers named after the pattern ns??.company.com. If you have 5 of them like you show in your example then I don't think I'd list all 5 as NS servers for each of your 800 domains (5 is really more nameservers than you need for a domain) but you could pick amonst them by, for example, using ns1 and ns2 on one domain, ns1 and ns3 on another domain, ns2 and ns5 on a third, and so on.

You should not define ns1.company.com through ns5.company.com as CNAME records pointing to the real names of those nameservers. NS records pointing to CNAME records has always been discouraged and might give you trouble. This answer says it's not actually forbidden by the standard, just not recommended.

So make sure ns1.company.com through ns5.company.com have A and AAAA records. If they aren't your servers then this means you will have to watch out for the server owner changing the server's address and update your A and AAAA records accordingly if you see it change.

If ns1.comapny.com through ns5.company.com aren't the servers' real names then it is likely that the reverse DNS entries (PTR records) won't point back to those names. This is perhaps not elegant and I would recommend against doing that for a mail server, but for DNS nothing should really care.

Another way you could handle this is, instead of having more nameservers, you can have the same number of nameservers with more IP addresses each. In other words, instead of adding ns6.company.com and ns7.company.com when you want to add your 6th and 7th nameserver, add A and AAAA records for the addresses of the new nameservers to some of the existing 5 names (e.g. if you have 2 new server IP addresses to add, choose 2 out of the 5 existing names and add one IP address to each). This way, all domains that are already delegated to the existing server [names] will get to use the new servers for free.

You can also use any mix of the two strategies: if you have 25 nameservers, have 5 different names with 5 different IP addresses each.