How do I detect (from C#) whether a mail server is available?

I don't know if you want to check outgoing or incoming server but basically all you need to do is to open socket to the correct port:
SMTP: 25
POP3: 110
IMAP: 143

Look at this msdn article - all you need to do is to try to connect to the server and if that fails then you know the server is not accessible.

http://msdn2.microsoft.com/en-us/library/system.net.sockets.socket.aspx

thanks.

Now is there a chance it will fail to connect because the mail server is busy, if I have a mailing going on, for example?

Or does it at least know the server is operational but slow to respond?

So are you saying, using the "listening on a port" method, that if it's got a heavy load it might appear to be down?

It depends on mail server. Some will deny incoming connections at all some will accept connections. Generally if you can connect to the mail server's port you must issue proper commands and it mail server's job to execute them. If the server is not able to execute command it must report an error code.