Scenario to reproduce:

You have an 'old' page named Foobar. Adding links to this page from other pages by using Link browser > Search works like a charm.

Now change the title of the Foobar page to Foobar haz fun.
Afterwards, again use the Link browser from another page and try to link to the Foobat haz fun page. Now, the autocomplete menu shows the old page title Foobar. You can choose the proposed old page title, it works. You also can manually add Foobar haz fun to the field, and it works as well. However, this may become very confusing.

It looks like confluence is caching the page titles and this cache is not flushed appropriately.
After "some time" all goes back to normal - it looks like the cache get flushed after some time (if there is really such a cache).