The thing is, after my computer halts (and no wireless connections
are in use), I usually switch off the whole box by switching off
the power socket. So when I fire up the system, the modem + router
are usually just starting as well.
This is the cause of your problem. This is how booting seems to work.
During boot, Debian starts running the MTA (Mail Transport Agent)
which is Exim4 in a default installation. It is looking for the
network connection - this will be the internet. If your ethernet card
connects immediately to the internet, Exim4 will start seamlessly.
Otherwise, you will have to wait a minute or two until Debian gives
up trying the connection and starts Exim4 anyway.
I usually switch off the whole box by switching off the power
socket.
This is not a good idea with any system - you could easily get disc
corruption. Always shutdown normally using the display manager
command button (in gdm, kdm, xdm) in X, shutdown command or
ctrl-alt-del in a console.
This is the cause of your problem. This is how booting seems to work.
During boot, Debian starts running the MTA (Mail Transport Agent) which
is Exim4 in a default installation. It is looking for the network
connection - this will be the internet. If your ethernet card connects
immediately to the internet, Exim4 will start seamlessly. Otherwise, you
will have to wait a minute or two until Debian gives up trying the
connection and starts Exim4 anyway.
Alternatively, if you don't have a reliable internet connection on
start-up you can do "dpkg-reconfigure exim4-config" and select "yes" for
the "Use Minimal DNS" question at the very end. This will stop it
hanging on start-up, if the internet connection is down.