Rule error: "Cannot remove messages from the folder"

[Rick Charnes]

I have a rule where I chose "delete it" in the "What do you want to do
with the message?" box. That works fine, and places my desired messages
in the Deleted folder. Today I decided to change it to "permanently
delete it". For some reason now it returns an error "Cannot remove
messages from the folder".

Any idea why Outlook can't permanently delete a message via a Rule?
Thanks.