Music stored on the External SD Card is removed from playlists at reboot
After more experimentation, I've made a breakthrough. Ultimately, this all happens cause Android's Media Scanner will scan the internal SD for media at startup. When it finds Playlist files it attempts to import them into the system database but because the SD card takes a while to mount at startup and is temporarily unreadable for a while at boottime, when it tries to follow the path back to the music on the SD card it can't find the music since the SD card is still mounting. Instead of, yknow, doing anything logical like waiting for the SD to mount, it just erases the entries from the playlist. So to get around this stupid flaw in the system, you need to move all your playlists (.m3u/.pla/etc files) to the external SD card.

By moving the playlist files to the SD card, it ensures that they only ever get read once the SD card has finished mounting and the Media Scanner then attempts to scan the external SD for media. At this point it finds the playlists and follows their mp3 file paths back to the finally loaded Music folder on the external SD.