That's pretty much standard for all recruitment agencies in the USA and EU as they want to avoid being fined heavily.

I am not sure but in the UK employing some one without the legal right to work has no defence even if they had perfectly forged passports/documents.

I had to (as some one with all 4 grandparents being natural born uk citizens) have had to take my birth certificate to register at a local high street agency.