Actually, Twin Wasp, that's not true. There are records - books that a company keeps as to what aircraft was flown when, and often by whom. It's pretty easy to spot-check with a phone call to the company.
As to your question Pattupilot - it's not normal to inform the candidate you're going to do this - and really, it's not normal to take the time. Usually a simple interview can determine if there is padding in a logbook. That said, it might be routine for this particular company. It is normal to request ratings from the FAA and/or to view the actual certs in person.
Interesting that they said this to you. But hey, we're dealing with people here and everyone has a different method or style of screening.
Good luck! (and I wouldn't worry about what they said.)
Lori