Re: OK WTF!
Hmm, you may need to speak to the Steam guys @ Valve about this. Have you tried a re-install since? Also, do you get this error every time you try to play?
I had a weird thing happening - when I launced Sin:E with the Steam Games window open, Sin:E would sometimes go back to "preoloaded" status. When that happened, I couldnt run the game anymore - and the only menu option was to buy (or view preload info). Restarting Steam fixed it every time - my copy was pre-ordered and preloaded via Steam, no retail.
Since you have retail and not Steam DLed copy, I'd recommend (ignore if you've already tried) (a) trying Steam restart and see if it fixes it (b) Ask Steam to create a desktop shortcut, close Steam, run the shortcut (c) uninstall and reinstall the whole thing from DVD.
If you still have no joy, I'm sure one of the Ritual guys can help - or at least point you in the right direction for Steam support.