How can I fix the error message "Could not find contribution record" from PayPal?
You can create a fake initial payment on a recurring contribution and CiviCRM will handle the IPN properly.  Unfortunately, this is a bit of a tedious process.  

Fortunately, it's all documented on my PayPal and CiviCRM page.  See the section called Modifying an IPN to reflect an updated CiviCRM contact ID.  The scenario is a little different but the techniques are applicable here.