What I have had to do everytime I reinstall magento is to go into configuration of the store and reconfigure the paypal checkout, redownload the pem key, and reinsert the api username and password.
some good pointers on how to debug what is going on
1. Click on those links they sent you, and see if you can actually access the links. mine are restricted in my ssl.conf file to a location match coming only from paypal, so i cant. maybe you have prevented the access some how
2. Try to debug the log files from your (apache, I am assuming, logs). Mine are in /var/log/httpd/ and i have many different log files. You can actually log into your paypal and resend the ipn notification.
I would do that and "tail -f" the log files to see what is added.
read more here
and you can learn about testing your ipn here
It is also possible that your transactions are going through, but not notifying your magento system.
Have you ever thought about just calling paypal?
1 (402) 935-2050
honestly this is the only thing i would be doing, its also possible it could be a phishing scam