The next time you get the page-not-found situation, I'd be interested in seeing the PayPal_CURL log for the DoExpressCheckoutPayment step (the 3rd of the 3), as well as the URL that shows in the browser.

As to the missing emails, at least it's consistently giving both you and the customer the emails, or it's giving none. That's a good sign.

I'm not sure what's preventing your orders from being saved though. However, uninstalling all modules that are not actually being used will help prevent them from getting mixed up into the process, which does sometimes happen unfortunately.