That's not required - I just confirmed by adding an additional publication and having Alexa discover again without doing anything more. It found the new device and I was immediately able to control it.
So, something else had gone wrong in your installation - most likely to do with Amazon's poor caching of devices (mentioned in
the Troubleshooting section of the Alexa plugin docs).