Notes 8.5.3, as well as 9.0.1 does a name lookup on your local address book at your contacts and Recent Contacts. I don't know what was your previous configuration back at the 8.5.3 or why it didn't search contacts on the Local address book.
But you can try a thing that worked for me in my fight against many headaches that Recent Contacts brought to me (I also use other parameters regarding Recent Contacts, but this two may help you with your actual problem).
On the notes.ini client, you may add these lines:
TypeAheadShowServerFirst=1
TypeAheadShowServerFirstDefault=1
That will make that the name lookup goes to your server in the first place, so in your client you will see the contact from the server and below it you'll see the other from the local address book under a category called "Local Directory", very easy to identify. If you just press ENTER after writing the name of your contact, you'll be using the server one.
You can also send this parameters using a Desktop Policy
Hope it helps