If you have already removed the incorrect address from the recent contacts view and it is still showing or being pulled in by type-ahead you could run a fixup -f and updall -R against your local names.nsf and see if the that resolves the issue for you. There are other things to try as well but I will give you my take on recreating the address book.
1. From within the notes client create a new address book by pressing CTRL + N, keep the server at Local, give it a tittle and make the file name anything other than names.nsf (namesnew.nsf for example). Select the Personal address book from the template list and then click OK.
2. Once it is done creating the address book should be opened. Open your current address book and copy/paste your contacts and groups into the new address book. You should also go under the advanced view and copy/paste the locations and any other info that you feel is important (cross certs etc….)
3. Exit notes, browse to your notes data directory and rename names.nsf to namesorig.nsf (or whatever you want) then locate namesnew.nsf and rename it to names.nsf.
Relaunch notes and that should do it.