After some discussion with Rob, I realize that Al & I were talking about slightly different things....
We have indeed discovered some odd happenings when migrating from ISO-8851 / latin1 to UTF-8 encoding. This appears to manifest itself in various ways on upgrades. There's not always complete consistency with what happens and why. I did a LOT of reading on the issue and found that it affects many different software packages out there, not just CubeCart. I did more studying and found a solution that I know Al has tested on some of the upgrades he's performed directly. I don't know if the code is ready to be incorporated into the full release yet, that's up to him; but it essentially forces MySQL to rebuild the database contents with the proper encoding so that everything will be correctly stored under UTF-8 after the process.
I believe some it may have to do with upgraded MySQL DB versions as there are still hosts running quite old versions out there. If the V4 store was installed under an old version then upgraded later, it *could* explain why we only see the issue on some stores but not others. This is just speculation as it's very difficult to say without specific knowledge of every server it's occurred on, but from what I've seen, the modified upgrade script fixes the problem. Let's just hope you all kept a good copy of your pre-upgrade database