I know this sounds kinda whacky, but what about using a hidden frameset? In other words, have one frame load the page that runs your code to enter the info into the DB, and the other frame that houses the PayPal page...
I have never tried this because I am not sure if you can pass variables across frames, but hey, you never know...
Another whacky idea is to create a midterm page that enters the info into the DB, and parses the entered info back to the user (show something like: "This is the info you provided, click on the submit button to proceed to the PayPal checkout."
Instead of relying on their PayPal confirmation (which is something you can't control) force them to go that one step while on your own site first, before moving them to another.
One last whacky idea is to do a popunder and have your DB insert code on the popunder... You could write the code so the popunder disappears after the insert code is run and verified to have been put into the DB.