Most of us who are rooted and running GB ROMs have already been dealing with this for a while.
My suggestion? Switch to Google Voice for VM. I suggest this not just as a "workaround", but as very functional replacement for the standard VM service. After using it for a few months now, I can't see myself going back, even if HTC/Verizon were to fix the VM notifications.
There are a few nice configurable options, including email notifications when VMs are waiting. This is very nice for folks who, like myself, often have to work in buildings with no cell service, as I can still know when messages are left for me without having to powerup and phone and search for a signal.
Anyway, all you need to do is signup for a Google Voice number if you haven't already, make sure you have the Voice app, and then setup your Verizon account to forward your VM service to Google Voice. here are the instructions I used:
http://www.google.com/support/forum/p/voice/thread?tid=00a93855af6943b4&start=80
*I'm not saying Verizon shouldn't fix the VM notification issue (nor do I want to get into an argument about that), I'm just suggesting an alternative that does work, and in my opinion is better than the service Verizon offers. You opinion may vary.