Hmm, apparently I solved it somehow. By letting it rest for a while after wasting a lot of time, it suddenly clicked. Maybe someone else runs into the same issues, so leaving it here if someone else runs into the same issues.
- Changed user folder from `firstnamelastname` to `FirstnameLastname`. Somehow RekordBox recognizes the small letters while iTunes shows them in CamelCase. Or the other way around, not sure.
- Selected all tunes in Collection inside Rekordbox, deleted all of them. 4300 tunes, but as they were doubled, they were 8600. Didn't really take a long time, as they were just references to iTunes rather than deletion of 8600 mp3s.
- Restarted Rekordbox, just to be sure.
- Restored a Rekordbox backup from my old Macbook. This was around 900mb, for 4300 tracks. Once restored, had to restart Rekordbox again as it asks you to do so.
- Unable to load tracks, as tracks still referred to `.../Firstname/` rather than my current setup in iTunes, which is `.../FirstnameLastname/`. Clicked 'File' -> 'Find missing files' -> went through my folder structure and found the tune it asked for. Rekordbox then asked me to find other files in the same section. Clicked yes; then it took a while to find 4300 tunes.
- Once that was done, everything was back to normal. Analyzed all new tunes that weren't there and it worked again.
I guess the biggest problem was solved in step 1 already. Changing the capital of a letter doesn't influence the folder structure much, but it was the solution to get rid of rekordbox/itunes struggles. It also helped that I had a backup, ready to restore. By reminding the tunes, it automatically picked up the right iTunes library.
I'm currently exporting to an external drive, which is taking quite long though. I guess it's rewriting there as well or something, as I've read somewhere that rekordbox links it to the original path so the syncing of beatgrids back and forth works correctly.