When you go into Unity Administration, and look at the settings for that particular Subscriber, what does the MWI status show? (I believe it's in the Messages section) That should represent Unity's view of whether there are messages or not. In your situation, it should show "Off", since you have said there are no messages.
In the same location, there should be a button to synch up Unity's view of the MWI with the MWI. Click on that to see if it resolves your issue.
If not, here is a link to the MWI Troubleshooting Guide:
http://www.cisco.com/univercd/cc/td/doc/product/voice/c_unity/unity31/tsg/tsg31/tsg_0500.htm
Eric
