Why did the 10.8.3 update disappear from the App Store after I restarted my new Mac?
I had exactly the same issue: Brand new out of the box MacBook Pro 13" 10.8.2 preinstalled. Went through exactly the same process outlined by the OP.

Resolved by:


Closing the App Store
Restarting App Store 
I then went to Store > Check For Unfinished Downloads


The 10.8.3 update then reappeared and I was able to redownload and install.

Hope this helps