Alright, lemme make sure I got this right:
1) Your contacts that were stored on the phone disappeared.
2) You had them all backed up on Gmail, however all phone numbers were written in the Notes section rather than the Phone Number section. At this point you have 135 contacts on your phone, all from your Gmail account.
3) You followed the post to export/import your contacts, so that now you have the original 135 from your Gmail and all 135 again that are actually on your phone.
In this case, it's relatively easy to get rid of the Gmail ones. While in the Contacts app, hit Menu > Accounts > the Gmail account the contacts are in > Uncheck "Contacts".
I don't know how much space that would take up (probably not much, it's only text), but it's not completely insane to not want doubles of everything - I've been cleaning up my Contacts for that reason as well. And as far as the lagging Gmail goes, I've heard the Instant Search thing may lag some people. It's a shot in the dark - especially since I don't see anything about it on the Contacts page - but you can try turning it off.