A small update for anyone having similar issues: I decided to remove the problem at the root, so I fired up Tag&Rename and had it rename all files with the following tree structure:
Artist
->Album
-->##-TrackTitle
(If you use Tag&Rename or a program working with the same tagging system, the string to get that file tree is %1\%3\%6-%2)
I then removed ALL the tags (this part is important), stuck all the files in a "music" subfolder and access them using the file browser instead of the database. If I want to do random-all I long-press on the "music" subfolder and select to add to the current playlist, then play it on shuffle.
This works great for selecting specific music as long as you're happy doing it by artist-album (and don't care about browsing by the other fields Database mode offers), and it's actually faster than database mode on shuffle-all.
Lastly, it might be that the fault for all this is Tag&Rename's - it's worked so far on other players, but otherwise I can't really explain it. I thought of retagging everything with another program, but as it's currently set Files mode works perfectly fine for my use, so I'm not looking forward to wasting more time on this problem.
Note that if your database is getting stuck on your tags, just using file mode isn't enough, as it'll try to load the tag anyway when the file is loaded. You do need to wipe the tags from all the files.