Where I work we have forced pushes disabled, but allow "delete the branch/recreate the branch" as an inconvenient workaround for people who really need it. Of course the remote is set up to never prune the seemingly now unreachable commits, and it keeps a record of what branches exist/have existed and what they have been pointed at. I think if you push sensitive information you can get it actually removed if you contact the VC team, but everything is set up to be auditable and safe by default.

I agree with your "always rebase" method, the readable history is well worth it alone.