In Norway, employer even have only limited rights to access things like your employer owned devices if they are personal to you, on the basis that it would be an invasion of privacy unless a lot of steps have been taken to prevent you from accessing or storing personal information on it.
Though in a case like this where they have evidence that implies wrongdoing, that would be sufficient to search equipment the employer owns or have financed. The barrier for searching private equipment is massively higher, though, and would normally require going to court.
Personally I'd never consider working for anyone that demanded a clause like what you outlined. I understand their liability concerns, but the at the same time if they won't trust me, then I can't trust them.
Coming from this background the extremely lax privacy protections guaranteed for US based services are always somewhat creepy.
On the other hand, whenever someone questions these lawyers about such clauses, they always tell you, ha, this is completely normal, it's boilerplate.
How does this work???
Though not all Google employees sign this, just the Project X experimental ones.
So in this case Uber presumably has a similar clause in their employment agreement and are searching relevant employees devices for evidence of the files.