Search for cancelled Paypal recurring contributions
There are several things things at play here:


Before v 4.7, when recurring contributions failed, an installment was not created - this behavior was changed as of 4.7 as described HERE, so this explains why you aren't finding any failed contributions in your system
Using basic searches on contributions will result only in the installments (i.e. individual contributions) - not the actual subscription, so unless you edited an installment and marked the status as "Cancelled", this explains why you aren't finding any cancelled recurring contributions in your system - there is a report that will allow you to search on and view the status of the subscription itself in CiviCRM, but not sure as of which version the report was made available - check to see if you have a "Recurring Contributions Report" available to you under Administer > CiviReport > Create Reports from Template > Contribution Reports
Even if you do have this report, other than the initial creation of the recurring contribution, no further information is communicated from CiviCRM to PayPal, nor are changes to the recurring subscriptions directly on PayPal reported to CiviCRM - you would need to update the corresponding recurring contribution manually in CiviCRM to reflect the those changes (being sure not to toggle the "Notify PayPal" option when doing so b/c this will return an error since it has already been cancelled on PayPal)
There was a point in time where cancellation of a recurring contribution from CiviCRM was not communicated to PayPal, and I'm not sure if this was ever resolved, so to play things safe, if you cancel a recurring subscription in CiviCRM first and toggle the "Notify PayPal" option, log into PayPal to confirm that the corresponding recurring subscription was indeed cancelled
You need to login directly to PayPal to make changes to the payment amount, card, frequency, etc. for those to take effect - you are also able (if memory serves me correctly) to make those changes in CiviCRM, but again, these changes are not communicated to the payment processor


Hope this helps!
Tamar