I discovered that I could actually add many of the games I bought on physical media in Steam and/or other services by using the serial key inside the case. Still it doesn't help if you can't find the case either... and not all games could be activated this way.
Hmm - that's handy. After a move, I'm sure I have the disc somewhere ... it's just in some box somewhere. I will have to give that a try when I find it.