What could you possibly do to mitigate that risk? Deactivate your accounts and re-register with a different email address? Get a new credit card because the last few digits were compromised? Move to a different house? This is a serious question. None of the stuff potentially compromised is supposed to be 100% secret, even your billing address.
Also I would blame Netflix for allowing account hijacking without secret information, not valve. Sure leaking personal information is bad, but Hell you can't blame valve for letting people get into my Netflix per se when my co-workers and friends could just as easily get in without the leak.
"Hi, this is Steve at Valve support. We've noticed a problem with your account which could lead to us deactivating your account. If you could just give me the full credit card number for the card you use with your account, the one that ends in 7328, I'll get that sorted for you."
I'd only need telephone number and last 2 or 4 digits to do that much. More data would only help to make it more believable and since this is a cached request from the store, if I can name a game the person ordered literally only an hour ago, I could probably fool a lot more people than this kind of exploit would normally catch.
Yeah, you can't change the data that Valve allowed to leak easily, but you can damn well be careful to look out for someone trying to exploit it.