I've re-registered my software token several times due to reimaging my phone, and every time - including the first time - the emergency removal code has been displayed on the web page that is displayed upon login immediately after linking the additional authentication token (AAT) to my account:
I keep that key, along with the rest of my account information, in a Keepass 2 database for easy retrieval for situations exactly like this.
I've never had to contact SE support for this, but in their defense the reason you got the "I'm not sure, keep your eyes open" answer can be explained in two words: outsourced support. Clearly their training doesn't include going through the user experience of linking an AAT to an account. This is something that maybe we can suggest to SE that they feed back to their outsourcing provider to fine-tune their support.