Q: Mail.app very slow to complete addresses

You are not alone. I'm seeing exactly the same issue. Glad to know that you have reported the problem and I hope that it can be resolved soon.

I tried to delete the file MailCents-v4.abcdmr under the directory /User/YourUserName/Library/Application Support/AddressBook, then it become speedy in auto completing the address. You may want to try and see if it helps, but you will probably lose all the email addresses that are not in your addressbook.

Thanks this works for me too.

From looking in Terminal at this file, it seems that the file I had previously did not have the Read permission for user and group enabled.  This can be enabled with "chmod a+r <file>".

When I have Mail.app recreate the file it seems to create it with Read enabled across the board so this is probably right.

Having enabled read permissions the address complete times are much improved however still not instant.  The old version of the file was 131k where as the Mail.app recreated version is only 40k and gives instant auto complete results.  As pointed out above, the difference will be the addresses not in your address book.

Wonderful! Worked for me, too.

I was having the same problem until I tried this slightly different solution: https://discussions.apple.com/message/19058957#19058957. Address completion is now back to its normal speed.

Worked for me too, although the file I removed was MailRecents-v4.abcdmr . Presumably renamed with the switch to Mountain Lion?

Thanks RHYC that worked for me too!