My VPS provider has "lost" the DNS records that I entered into their control panel.
Do these exist on my VPS ubuntu box itself?
How can I retrieve these?
Unlikely unless you were managing your own DNS server(s) - if you were managing your own DNS then all that would have been entered into your host or registrar's control panels would have been your name server addresses and names.
Agreed that it's very unlikely the records were stored on your VPS itself.
Depending on what your provider has done, it may be possible to get cached copies of the records from the slave DNS server(s) configured for your domain by using nslookup or dig. If they've already created new (empty) versions of your zone file(s), then recovery is likely effectively impossible.
If your provider can "lose" data like this, you should pay careful attention to your own backup strategy for the information on your VPS, because the provider probably doesn't have a backup in the event that something awful happens.