While a different company and set of circumstances, I would occasionally run into this sort of thing when I repaired Apple computers for a living. I would say the "tricks" I learned for that are basically pretty universal.
The more evidence you can provide to support your particular claim, the better. If you have 10-20 emails showing you purchased 10-20 different games, send those along. If you have a game you activated with Steam you can take a photo of, send that too. If you can find the email from when you signed up with Steam, send that. Anything that supports your assertion, no matter how tangentially, you should send along.
If you think about it from the perspective of a Valve Steam CSR, then if they're being snowed under with evidence from you, either you are an extremely dedicated account hijacker, or you are the legitimate "owner" of the account. Not to mention it helps them in the game of cover your ass. In the event that you really are a really dedicated hijacker, they can say, "Look at the amount of evidence that they sent me! It was perfectly reasonable for me to assume this is the real account owner." You help them, they help you, everyone is happy except the account hijacker, which is the way it should be.