I thought that when the plugin shuts down it saved the config, but it seems like this is a myth?

When I tried to reproduce this I could not.
I changed the config when the server was not running and loaded it: the loaded config had the values.
I changed the config while the server was running and restarted the server: the config file was not overwrriten and properly loaded the values set in it.

When I check the current code, the config is NOT saved on shutdown, and there are only three cases when it is saved:

• when the config does not exist on startup, it is recreated from defaults (standard saveDefaultConfig)
• when /ph config set <key> command is used
• when /ph config set <key> <value> command is used.

https://github.com/crashdemons/PlayerHeads/blob/0e957344d38cab652371f20bd5c5ca88d245dda4/PlayerHeads-core/src/main/java/org/shininet/bukkit/playerheads/PlayerHeads.java

So the config should never overwrite except when using config commands ingame.

This would make sense if it was old behavior but checking old code from Dragoboss (3.x-min) seems to imply it wasn't an issue then either.
https://github.com/Dragoboss/PlayerHeads/blob/b92503f7f2e92ed44107e639e39b2a66354c4ed4/src/main/java/org/shininet/bukkit/playerheads/PlayerHeads.java

So, was this ever an issue? people certainly complained about it and I always assumed it was the case - but there is no evidence it ever was.

Checking the code in 5.2.3 with JD (around the time of the original Issue), there is also no code forcing a save on shutdown.
So nothing seems to have changed since 3.x