This can occur when another program has registered itself as the default application for browsing the web. You must re-register Internet Explorer as the default browser.
Start Internet Explorer
Select the Tools->Internet Options menu
Select the [Programs] tab
Look for a checkbox labelled "Internet Explorer should check to see whether it is the default browser"
If this checkbox is not ticked, then this is the cause of the problem, so tick it!
Click OK
Close Internet Explorer
Re-open Internet Explorer
Close Outlook Express
Re-open Outlook Express
I checked what you said.
The only check box is "Tell me if Internet Explorer is not the default web browser" Above that it says "Internet Explorer is the default web browser"
This is the new Internet Explorer update which just came out, and now that I think about it this started around the same time.