Upon setting up a “send as” permission a mailbox for a user I got stuck. Even though the permissions on the user object were correctly setup for “Send As” when trying to send as a user with Outlook 2010 I kept on getting an error message.
After double and triple checking the permissions I concluded it must be caused by Outlook 2010. So I upgrade to SP1 and the problem went away, it appears it was a bug.