I also have an auto-updating feature built into my PyInstaller application that detects a version mismatch and then calls a support (updater) application that essentially swaps out the old app with the new one.
In order to resolve the error you are running into, a separate PyInstaller app of any kind must be executed thus creating a new _MEIxxxx folder. This will "trick" the OS into moving on to a new _MEI naming convention.
My theory as to what happens when running for example, MyApp.exe, a folder is built and the OS for some reason get's stuck with its reference to that folder for MyApp.exe. So, the next time that same app is executed (within the chain reaction that is started on the update), it will try to use the same "randomly" generated number.
In your order of events, I would suggest something like this:
Run MyApp.exe
Oh no! An updated is needed! Execute our installer application and close MyApp.exe
Once our original app is closed, replace MyApp.exe with the brand new one
Now, either run a PyInstaller application of any kind that is not MyApp.exe (this will create a new _MEI naming convention) or for bonus points build your installer (updater) application using python and PyInstaller which will flush out the old _MEI folder name
Launch the new MyApp.exe
Close installer and our separate app we used to change the _MEI folder names if needed
This was quite a tricky one that I could not find anyone else running into this issue. As long as I run some sort of alternative PyInstaller app that is not the primary app, I avoid this error.
Hope this helps! Cheers