My two cents
If they are anything like our DBAs they will have refused to do any sort of query and just copied one of the overnight backups onto disk.
A company I worked for was charged £2000/day for technical consultants (of which about £200/day went to the worker) so I wouldn't be surprised if the £5K quote was for one days work.
Just how big is a database of 25 million records? Our database is 250 MB and I wouldn't call it a big database. Can you get 25 million records on a couple of DVDs?