I see no obvious reason for there to be any problem with emailing when the PayPal module is sending vs anywhere else in the cart. Unless the email addresses are bad and being rejected, or something like that.
I used Paypal Push addon, and when I completed the pending order that way, the emails got sent. Do you think there is still "something" missing in that PayPal script, and thus emails are not being fired when orders are getting completed naturally?