Basically, you're right. The verification thing is invoked to provide convenient evidence to get rid of someone they already want to get rid of.
Trust only goes so far. If a company does not have good cost control and verification procedures, they can and will get robbed blind. Heck, the cash register was invented by a bar owner who suspected the bartender was embezzling in a blatant and ruinous fashion.
Why does it even matter why they take the time off?
Make a stupid policy, get a rational response from employees.