Upgrade to EhxVisited (sleazyfork.org/en/scripts/377945)
3.2 update:
Sounds like the perfect tool, but, I don't know a damn thing about it. :(
It seems the issues caused by opening multiple tabs simultaneously is due to the string being read by multiple tabs simultanously and then rewrote over simultaneously. There's maybe another possible workaround by using a storageevent listener, but it does look like moving to a database is the best solution, especially when the list of visited pages starts to get big.
I don't know how to use it either, but I might try to put together a version with indexdb. If I get it working I'll let you know.
Requires update
Requires update after new format changes, doesn't work on extended and thumbanil modes.
On another note, have you considered moving the database to a IndexedDB format? It seems more appropriate than a string.