Sales taxes in the US are truly and insanely decentralized.

The US has thousands of independent sales tax authorities with their own laws and regulations about how sales tax must be computed and displayed. These jurisdictions overlap, the sales tax you pay may be the aggregate of multiple different sales tax authorities between which there is no coordination.

Rounding to the nearest 5c or whatever creates a situation where in many locales it would be impossible to comply with sales tax and pricing laws because different tax authorities requiring mutually exclusive ways of making this change.

This creates an obvious need to change the law. This is not trivial because they are often written into statute or constrained by constitutional processes. It requires thousands of jurisdictions to all change their laws at the same time in the same way, which is effectively impossible. Even if it weren't the process would require several years. In many locales it requires a democratic vote -- what if the voters vote against it? Courts aren't going to let the government ignore these requirements because it would be inconvenient.

It really is a "herding cats" problem. There are many other things in the US that effectively can't be changed because there is no central authority to overcome coordination problems by fiat. Even at the level of all 50 States, resolving these kinds of coordination problems typically takes several decades.

> the US has thousands of independent sales tax authorities

The US does not have thousands of independent sales tax authorities; administrative subdivisions of states are not independent, or even sovereign in the sense that states (which are also not independent) are, and can be dictated to by the state they are in, if the state decide there is a need, such as an urgent common problem that requires a coordinated solution.

> It really is a "herding cats" problem.

It's not, though. It's a "convincing cats to find shelter when it rains" problem, that you are trying to make harder by inventing the nonexistent need to also gather them in a herd. They aren't in a herd with the penny as the smallest coin, and they don't need to be in a herd if that changes to a nickel.

> Even at the level of all 50 States, resolving these kinds of coordination problems typically takes several decades.

There is no need for a coordinated solution between all 50 states, just as there is no coordinated policy on sales tax now between all 50 states. All that is necessary is that there is a solution in every place where the current tax policy would be problematic without the penny. There is no need for the policy to be the same in every jurisdiction with sales tax, just as the status quo policy is not the same in every jurisdiction with a sales tax.

> effectively impossible

Let’s assume you are correct. It is impossible to ever make this change for reasons X, Y, and Z.

What happens when stores just can’t get pennies anymore? Does the sky fall?

Coordination problems become easier when there is a pressing need to solve them.

If pennies are phased out, companies need to figure out how to do business without pennies. If they can't find a legal way to continue business, they will tell the relevant legislators that the laws should be changed. If the legislators don't see a reason to change the laws, the companies will probably stop doing business in that jurisdiction. If the legislators still don't see a reason to change the laws, then the outcome is probably what the local residents wanted.