My entire store is basically built around the ability to store your game's settings but my solution is to store it online under a user account.
The big PRO here is that your data is synced across all devices you play on (i.e. you can play in your browser then pick up your phone and have the same progress/settings on there or vice versa). The big CON here is that you must store all their data in your own web space. Nevertheless, that is my approach.
I was actually surprised to find this topic because when you read the Unity docs (or at least back when I read them in this regard) they stated that the DataPath is relative to your game and can thus be overwritten but the persistentDataPath was defined as a path based on the platform you were playing on (i.e. the path is the same on all phones, on all Windows system, on all Mac desktops etc) specifically for the purpose of having your data persist between updates. If you are saying it isn't doing that then that truly is weird...
Thing is, though, the actual name of the project and developer determines where the data is stored so just make sure you don't change the name or the com.myname.gamename settings in the PlayerSettings and as far as I am aware, that SHOULD be the end of all your woes! :O
Note that when you build the app, a GUID will be generated based on the Bundle Identifier, and this GUID will be part of persistentDataPath. If you keep the same Bundle Identifier in future versions then the app will continue accessing the same location on every update.
and of course on Macs
user data is written into~/Library/Application Support/company name/product name
Normal DataPath though...
WebGL: The absolute url to the player data file folder (without the actual data file name)