No tax? No tax credits/benefits to staff.
I've thought about this quite a bit (companies moving their registered office to avoid tax) and here's what I reckon a govt with a brain should do, although admittedly its unlikely to impact Google staff.
Tax credits are just a hidden subsidy to companies right? Allows them to pay less and the taxpayer (personal or corporate) picks up the bill. Same with quite a lot of other "benefits" too.
Now at this point you can go two ways -
If the company doesn't want to pay tax in the UK then NONE of their staff should be paid tax credits. The company should be made to state in all recruitment adverts that since they avoid paying tax in the UK that no positions within their company are eligible for tax credits or benefits.
Alternatively the company should be forced to pay the tax credits/other benefits to staff.
Either way it pushes their costs up and makes them look like scum :)
Don't want to be in the UK tax system? Fine, then don't expect ANY of the upsides (not that there's many) of being in it, and you especially shouldn't expect the poor PAYE sods to subsidise your company profits!
Of course since all these companies do to make issues like this go away is hire a token troughing pig (AKA a Member of Parliament) it'll never happen.