You'll want to revert the deletions and use access= tagging to correct those paths. The Trail Working Group has a good write up about things they've learned and, unfortunately, deletions are almost universally problematic.

https://wiki.openstreetmap.org/wiki/United_States/Trail_Access_Project

Definitely reach out if you have any questions.