CDOSYS breaks after removing Outlook Express.

Yep, that will do it.  There is a relationship between CDOSYS and Outlook Express.  So, you should not remove Outlook Express if you ever expect to use CDOSYS or have anything which uses CDOSYS work properly.  Some people get very ambitious about security and start ripping-out software which they don't think is needed - however, Outlook Express is not something you would really want to remove.  Outlook Express sets the defaults of CDOSYS  with its default profile.