Windows Server 2008 without telnet client - how to test connecting to remote ports without installing anything new?

Nope. Either you're walking them through installing the telnet client native to Windows, or you're having them install Putty or a similar app. The functionality was deemed a security risk and so was turned off.

Windows 2008 has PowerShell v2 I think? If so, email them this powershell script :

:: powershell script
try { 
  $tcp=new-object System.Net.Sockets.TcpClient 
  $tcp.connect("localhost",25) 
  $tcp.close() 
} 
catch { 
  "Exception occured" 
}

You could use a browser and go to http://mailserver.tld:25

Naturally you won't get a web page back, but IE for example has a different error page for 'failed to download page' vs 'can't connect to server' which is how you would decide if connectivity was established or not.

I have spent quite a while on this issue as well. The best thing I came up with is copying down the the PuTTY executable.

There is a native telnet client to windows, you just have to install it. It takes a few seconds and won't require any media.

If you just want a dumb .exe use putty, but i find its gui much more annoying than just typing 'telnet blahblah'