First question: did you buy the game
from Steam, or from a third party key (re)seller? In the latter case, you might just as well start your travel through the support process, with having them check out whether that key is actually valid.
Otherwise, what do you see when you log into your Frontier account (on frontierstore.net) in the "
My Downloadable Products" section (and possibly the sections listed below)?
Edit:
link to support