Problem appears to be a non-problem.
Looks like all that was required was to sync again from Nokia suite. I was afraid that it would create doubles, but I finally decided to just risk it and was pleasantly surprised that no doubles seemed to be created. The sync process also completed in about 2 seconds so I'm guessing that Nokia suite figured out it really didn't need to sync all those nearly 800 messages.