You using DHCP to server out the dynamic addresses? If so it sounds like you need to a full DNS and have DHCP update this when it serves out the addresses. Its not something I've done but I know some people on the Bristol & Bath Linux Users Group have, you can register at
http://bristol.lug.org.uk. You might also want to check out
http://www.linuxdocs.org to see if there is a HOWTO...
The problem I've had in the past with slow telnet connections has been due to trying to resolve either the servers hostname or the hostname of the machine that is initiating the connection... (at server side in both cases)
HTH
Jamie...