In a Exchange user's mailbox they have (under 'Favorites') created a Search Folder to show all 'Unread Mail'. And this works fine.
However, from this Unread Mail search folder, when they attempt to Flag a message, they get the following error: "You don't have appropriate permission to perform this operation". Other times it does toggle the Flagged/Completed description field in the message, but the flag icon next to the message in search folder stays 'lit'.
From the normal Inbox folder, the user is able to Flag the same email that caused the error previously successfully.
To confirm: all of this is from a single user, looking at their own mail. There are no shared mailboxes in play here.