You may want to also re-index their account. I have seen this happen before and a re-index sometimes solves it.
Linda Pagillo
Mail's Best Friend
Email: linda.pagillo@mailsbestfriend.com
Web: www.mailsbestfriend.com
Authorized SmarterTools Reseller
Authorized Message Sniffer Reseller