I have just installed BES 4.1 on a fresh box. As soon as I add the very first user I get the exact same messages in my application log.

Event ID: 20265
(user@domain.com) MAPIMailbox: CreateSearchFolder - Open folder failed (0x80070005) failed.

Event ID: 20265
(user) MAPIMailbox: GetSearchRootFolder - CreateFolder(1) (0x80070005) failed

Event ID: 20265
(user) MAPIMailbox: ~MAPIMailbox - DeleteAllDeviceSearches (0x00000000) failed

Event ID: 20154
User Doe, John not started