A hard reset fixed this for me. Have you tried that?
The issue is something that creeps up over time. A hard reset seems to fix it, but in reality it just hasn't occurred yet.
I'm on my third handset (replacements unrelated to this issue) and it is better but the messages lag still creeps up now and then. With this last one I didn't sync Facebook or restore my texts (I have ~25,000 of them). While it's better, there will still be occasions where messages will take 30+ to load or Contact Caller ID doesn't work.
It's definitely something they changed in that last update. But there is really nothing to report to HTC as there is no way to narrow down what might be causing the problem. Someone posted that Facebook was causing the issue a few weeks back but taking that out doesn't fix it, but it is less severe. Not being able to sync Facebook is ridiculous though. Even my underpowered Palm Pre had no problems with that.
The most frustrating thing is that disabling other stuff on the phone doesn't help at all. I would deal with a crippled device for a while to have properly functioning phone/contacts/messaging, but at the moment, seems we're just SOL.