How do most game companies test their stuff fully when they may not have the skills to beat the game?

They always do, eventually... But if they don't, then maybe the game is a little too hard.

We don't have a QA forum, so I'm putting this in Breaking In. MS, please read FAQ 5.
Lukey is right in one respect: if the game is too difficult for QA personnel, then it's not suitable for the marketplace, and needs to be tweaked.

How do most game companies test their stuff fully when they may not have the skills to beat the game?

The certification process for major publishers include requirements that testers can achieve every trophy and award without cheats, including with the game if it has a win condition.