Unable to sign out of iCloud; linked to old email that no longer exists
After spending over an hour and a half to Apple UK's support, and eventually getting transferred to a senior advisor from their US-based support, it turns out that I may have uncovered a bug in iCloud that has since been forwarded to the iCloud Development Team.

The old email address had been used as my Apple ID for around 3 years before I changed it. Rather than add an additional one (as I was deleting the old email completely), I change the primary Apple ID; however I neglected to change it for iCloud (I wasn't actually using iCloud for anything, so I didn't think about it). As a consequence, iCloud is still associated with the old Apple ID email, and it wouldn't let me sign out of iCloud unless I signed in with the old Apple ID so I could disable Find my iPad so that I could sign out.

Now, here's the rub: for whatever reason, Apple have no record of the original Apple ID email. None at all. Normally, as @Tetsujin pointed out in his comment, I should be able to sign in to my Apple ID with my old email even though it's no longer associated with my account, because there should still be a record of it on the system. However, because (for whatever reason) it seems to have been completely purged from Apple's records, there is effectively no way for me to actually sign out of iCloud.

Apple have admitted that this never should have happened, and they have passed the details of the case on to the iCloud Development Team... so I may be indirectly responsible for another iOS9 update. Sorry.

In the end, my 'solution' was to abandon the original iPad and set my iPad Mini 4 up as new, manually transferring my apps and settings across, using the old one as a reference.