I was running into a very similar situation where I could not get Alexa to see any of my tagged devices. I had put off the port redirection as I had read both positive and negative reviews of implementing it. I can tell you that once I enabled the port redirection, deleted my items from alexa.amazon.com then put the binding in discovery mode, and finally I clicked on the big blue discover button on the alexa website…after discovery was complete…like magic Alexa was back controlling the house.
