Please write which PayPal Module you are using (Name and Link would be usefull), that will help providing you better help.
I had the same problem. But I do not know wether or not you are using the same (outdated) module as I did. So please post your version so that I can compare if I have a solution or not. In my case (an outdated module, name "paypal", link not known any longer) it helped to have the held orders extension and to provide a BOLD MESSAGE TO THE USERS THAT THEY NEED TO CLICK AFTER PAYEMENT TO RETURN. the last one all in caps did made the job in about 75% of all cases. the other 15% you get payments but you have no orders, so you can take a look in held orders which one was payed.