I've had emails arrive from eBay really late as well. Like confirmations that I've bid on an item which arrive after I've won it and paid. Or the item watch thing which notifies me after the item has expired etc... I don't trust any of the eBay email functions really just because it's so useless.

Don't know about the postal order item but the paypal one you should be able to complain to paypal.