these cheap staff probably dont have the confidence to claim linux experience.
Unfortunately, they often do claim this, and too often with no one in the hiring process competent to see through their bluff.
IMNSHO, exaggerating on a resume or job application is demonstrating that you can't be trusted and shouldn't be hired no matter whether you could be used for your other skills.
Likewise, HR setting up job requirements that realistically one or two people on the entire planet could fulfill is counter-productive, and the underlying reason for all the lies and exaggerations. If you want someone to work for a non-superstar-salary, you need to lower the requirements until people who actually fulfill the requirements will apply, not just the liars.
I'd much rather work with a junior admin with 3 years of actual hands-on experience than one with an Ivy League degree who tried dual-booting ten years ago. And not because of the price, but because he could possibly get the job done.