Are you using a MAPI profile of another local user on the machine? And when you are getting it work from the Console is that User logged in to the machine? If so then you are possibly experiencing on old COM/DCOM problem whereby the registry hive for the user that the component is run as is not loaded, you can test this by creating another no-op service that runs as the user who owns the profile and running it or running your original service as that user.

Alternatively it could be some problem with the permissions on the MAPI component - you can check these using the dcomcnfg tool (just start it from the command line).

Or you might simply just be experiencing the problem described here

/J\