While Mac Mail is simple and works, it has a problem syncing flags with Microsoft Exchange server. It can add messages as flagged, but when removing the flags, the messages will no longer be shown as flagged but the counter will still continue counting. What is the point of flags if they are always flagged!
The one solution that worked for my from the Apple Discussion Threads is to bounce Spotlight form the terminal:
cd ./ sudo mdutil -i off sudo mdutil -i on /
This is not ideal and I suggest cleaning out the flagged messages (or remembering what they are) in case all the messages get removed.
Sources
Man and Keyboard 