For anyone reading this, Plex is smart enough if you move an existing Library file from Path A to Path B to realize you actually moved it, and that it's not a new duplicate. So while what @josefilion did worked, it really doesn't need to be done that complexly, or at one go. I recently moved from one huge folder with subfolders to one with A-C, B-D etc subfolders because it was taking Windows a long time to list the contents and I basicly just grabbed a few hundred folders at once with cut & paste to the new subfolders and me having "Detect changes" enabled in Plex made it pick up the moved files almost instantly.
So basicly: No need to turn off Plex. Just move your files how you want as long as they are not currently being played / scanned and you move them within the Library root folder.