I also have this issue, and can confirm that once cleared (home > settings > call > clear...), the notification comes back a bit later.
In conjunction with this issue I also had a weird camera issue (the picture, regardless of settings, manifested as a purple solarized image).
I took the phone into the store here in Overland Park today over lunch, and they told me that for the voice mail notification alone, they would need to reflash the phone. They were backed-up by about 3 hours, so I had to leave the phone with them and don't have it back yet.
I'll let you know how it turns out.
Footnote:
On Friday, a few hours after taking the Gingerbread update, the camera went wonky. I hard-reset the phone, and it was fine until Sunday, when the issue recurred. I hard-reset again on Monday, and again camera was fine until yesterday (Wednesday). Very frustrating.
Note that the rogue voicemail notification survived both hard-resets.