I've managed to find a solution.
The following is based on using Gmail via IMAP in Outlook 365 (probably the same is true for Outlook 2016).
Log into Gmail and allow the Spam folder to be visible in the IMAP client. To do that, go to Settings -> Labels, find the Spam label, and make sure the Show in IMAP next to it is ticked.
Open Outlook. Right-click on the root Gmail account folder, and select IMAP Folders. This will open up a new window where you can select which folders are being subscribed. Press the Query button, and once the folders have been shown, mark the Spam folder and press the Subscribe button. Click OK to apply changes and wait for the new folder to be visible.
Restart Outlook. You should now be able to delete the old Junk Email folder (it shouldn't be protected any more).
In other words it seems like Outlook NEEDS some kind of folder for junk email, but it also seems like it's not picky - if it can have the one from Gmail, it'll be more than happy to use it and let you delete the "default" Outlook folder. Obviously if you don't want ANY spam folders in Outlook, that doesn't solve the issue, but at least you're using the Gmail Spam folder rather than the Outlook one and you don't get the unnecessary extra label which is otherwise created in Gmail.
EDIT: Anyone know how to pick this as an answer after the fact? :/