This is the problem with using a remote checkout method like paypal payments standard.
Since the payments are not processed real time, there are some extra steps that need to be made.
the order should be stored to the database on going from checkout to confirm, but you should have a column in the order table for orderStatus and this should get set to pending.
You then need to configure your paypal account to make an IPN post on transaction completion. and configure the IPN page to update the order status in the database based on the IPN information.
see this page for details on IPN.
another alternative is to use PayPal Express Checkout, this is also a Free Service from PayPal, but has the advantage of processing transactions in real time.