You need a cart that fully supports paypal IPN (internet payment notification). Without this support you will run into the issue you are having. IPN post back to a predetermined page on your site information about the order. As soon as you get money paypal basically tells your website the status of the payment which resolves the issue of someone not returning to your site. I know OScommerce supports this.
Depending on your level of programming ability it is not that difficult to integrate.
Another vote for Oscommerce - it does all you want. You can also customize the return button that the customer sees at Paypal after paying to tell them they must click the button to return to your store. If after all this they still don't click the return you have the order logged anyway. Later down the line if you want to add another payment gateway there is usually a module to do so - you are not restricted like some carts. These other gateways don't have the IPN that records the order if the customer doesn't return,but you can add an Orders in Holding contribution that logs these orders so you'll always know what the customer bought even if they don't return with a non-Paypal purchase.