BB Bold 9700 :: Contact Names Not Recognised For SMS If Battery Removed

My Bold 9700 is not recognising the contact name for SMS messages properly. But it is a different problem to what others have described. When I receive a message, it shows the contact's name correctly (which was the problem others had I think).But then if I turn off the bb and remove the battery, then replace it and turn the phone back on, none of the SMS messages have the proper contact names - it just shows either their phone number, or their name if I have them stored on my SIM. What's more, this problem only occurs if the contact's phone number is stored with spaces and brackets in it [ie, +64 (21) xxx xxx].

I realise I could go through and add everyone to my SIM card or remove the brackets and spaces from contacts' phone numbers but
a) this wasn't a problem before (on 8310 and 8520) so should be able to be fixed
b) my SIM card wont fit all my contacts anyway
c) phone numbers are hard to read without spaces and brackets
d) it's such a waste of time!
My software version is 5.0.0.344 (which is actually later than what I can download!)