It is probably related to the profile (or its size). I have usually ~80 MB profile file. When I deleted whole history of contacts, it was slighly faster, then when I deleted many accounts (and thus many contacts), it became much faster. And when clean profile and only few contacts it's fast too.
I expect it iterates over all contacts for some reason (like it does when you are deleting or moving a group - which is completely insane - bad design). I wonder why it is better for you now...