This isn't so much of a question in need of an answer, I found the solution, thought I'd just write it down here so that others might benefit. Hopefully it hasn't been covered already (I did search!)
Over the last few months my contacts had become slower and slower to open and view, right to the point where yesterday just trying send a message to a friend resulted in "Contacts: Memory Full"
After much frustration, searching forums, and hair pulling with no luck at all, I figured I must have something on my phone interacting with the contact list. Turned out to be the "Conversation" app in some kind of insane memory grab, seems to only do it when you have a few additional directories under "My Folders" (One of those things I installed months ago and never used, forgot it was there)
Anyway, for whatever it be worth to anyone else, removing the conversation app fixed everything. I think this has been discontinued by Nokia or is no longer supported anyway.
The other solution was just to remove all the subfolders in "My Folders", though not very convenient when you have a few thousand messages all carefully sorted and categorized.
Cheers.
Brendan.