Do you have Office 2007 installed?
There's a known bug in that Office 2007 installs some language files that are incompatible with Outlook Express, producing the effect you have experienced.
AFAIK, it is not reversible, and MS have never fixed it (I guess they don't want people to use OE and XP any more).
Your options are either move to the full Outlook client with Orifice 2007 or get hold of a 3rd party spell-check add-on for OE.
SD