When deleting policies you have to be careful not to delete a policy that has dependents or you'll end up with an invalid store. That's one of the reasons why we haven't introduced hard deletion. Storage is pretty cheap and the tables are indexed so unless you have many millions of records, I'd be surprised to see any performance impact.
Since you're using principal policies, they are relatively safe to delete because they don't have dependencies. Once you have deleted records, you could call the store reload Admin API endpoint to refresh the cache. But, you don't have to do it. Those cached entries will eventually expire and get dropped from the cache anyway.