Yes, nameservers should actually be set up in pairs on the same C class, its makes some sense because there can be momentary delays (especially in a shared hosting environment) during a single request for one ns but when asking again (as in the case of 2 ns records pointing to same C class) the delay would often be gone. This goes against a certain RFC, maybe it should be updated.
Anyway,
back to the original question, I am a bit unsure of the first answer. Do you mean that all Linux
VPS Hosting's here are all on the same C class. I ask because I am looking for another one that is preferably on another C class.