word of caution here: since outlook refused to start because the pst was missing, this indicates to me that the pst file may have been where the mail delivery location was set to (in other words, the default information store). if this is the case, and you deleted that pst, your inbox will be empty the next time you do open outlook!!! I hope when you deleted it, its still stored in the recycle bin! if it is, restore it until you are sure.
if it was a blank pst, then no worries.
What version of outlook are you running? If its an older version then what I said wont apply.....
in the future, instead of deleting files like that, just try renaming it first. I.E. call it "outlook.old" instead of "outlook.pst" and test your results.
regarding the original problem, this is a very serious bug in outlook that has started since office 2003 and office XP SP3 were released. There is NO mention of this error anywhere by microsoft, the only references are by frustrated users. In the past I have fixed this by copy contents of the old pst to a new blank pst, but eventually the problem appears and happens every single time outlook starts. dont know what is prompting outlook to do this but there does not appear to be any fix.
if you are on an exchange server, leave your mail delivery location (valid on outlook 2002 and above) set to the server ("Inbox-Username") instead of to "personal folders."
if its a POP (internet) account, be sure to check in the "leave copy of messages stored on server" option.
in case outlook ever "breaks" again, your mail will still be there.