The message "Discovered new external address for our node" happens every time an external address enters the list of known external addresses of our node.
The problem is that this list of known external addresses is heuristic. It can happen that an address enters the list, then leaves it, then re-enters it, and so on.