In order to verify that a pay response is legitimate, PayPal provides a unique token for each request. This token can then be matched against payment confirmation requests to ensure that they aren’t being spoofed. The problem I ran into was that even the legitimate IPNs I received did not contain a pay key.
It turns out that PayPal sends two different types of IPNs. The first is configured when making the API request. The second is configured in the PayPal account under “My Account > Profile > Instant PayPal Notification”.
The first type, includes the required PayKey, the second does not. Simply configure your profile details to point to another url and everything should work!
For more info, check out this stackoverflow post: http://stackoverflow.com/a/12031887/522859