They could adopt Github's model, which seems to work well: when you rename something, the old name becomes an irrevocable redirect to the new name (at least, I think it's irrevocable, I haven't tested it), so all existing uses of the old name still work transparently.
I have broken GitHub links, I assure you they're not irrevocable. I transferred my project laughinghan/mathquill to its own organization, so the repo became mathquill/mathquill, and then forked it, unwittingly breaking all github.com/laughinghan/mathquill/* URLs: not commits obviously, but Issues, PRs, Commit Comments...my commit messages occasionally link to discussions in commit comments, all of which were broken. :(
Yes, you would need to publish a new version of the package with a different name. But the history of what happened (and consequently anyone depending on the old name) would be preserved.