Then restore your wallet.dat and you should see your coins. Immediately transfer them to the paper wallet. That will make your coins safe until you are sure your computer is clean.
This. If you wallet was stolen the fact that you didn't do it immediately likely means the coins are already gone but anytime a wallet is compromised one should immediately transfers full value to a new wallet (preferably one on another machine). Using a temporary online wallet like MtGox or strongcoin account is fine because speed is of the essence.
With 2+ copies of private keys existing it is simply a race of who gets a transaction into a block first. With a good thief you won't have a chance they will transfer full balance of wallet.dat to a new address in a matter of seconds. Maybe you got lucky and it was a "bad" thief.