The code (or any record of my purchase) was not available on the store site.
I finally found my SECOND code in a deleted email and entered it successfully.
Why is this even necessary? It feels like a leftover from the days of buying games on CD from a retail store and entering the code. Hey, SE, just have your lobby server ask the store server if I paid for the game and let me in..