I've used Exchange 2003 with a self-signed certificate, so I know it is possible.

First most basic questions: Are you using PR1.1 (or newer) and did you import your certificate into the N900?

This wiki page contains most of the information about common MfE problems, solutions, and what it is capable of:
http://wiki.maemo.org/Mail_For_Excha...rtbeat_and_FAQ