I have the same error - 0x80040115 i.e. Outlook 2003 not able to connect to Exchange 2007.

ipconfig /flushdns does not fix this problem.
restarting the exchange server information store service does not fix this problem.
Rebooting the exchange server does not fix this problem
changing the cache settings doesn't change anything.
All exchange services seem to be running correctly.
In outlook 2003 I've deleated the user and set him up again, so even the password has been reset.
I've run Office repair on this machine.

The Outlook 2003 machine ran just fine for months, no major changes that I can think of, it simply stopped working. Everyone else is on Outlook 2007, with no problems. This user doesn't want to learn outlook 2007 and I've no reason to push that issue. Exchange 2007 is a fresh install, so no upgrade/portability issues.

Outlook does not tell me if it is or is not online.

Hello and welcome to PC Help Forum.

I have moved your post to its own thread as not to confuse your issue with other peoples issues.