Prevent duplicate routes properly

* Guarantee lock when checking & adding a route
* Upgrade to a solicited route if one is seen