Beyond the fact that using TELNET across public networks is  
definitely a no no, is
there any way to work around the <CR><LF> or 'double return' issue  
that seems to
plague Windows 2K/XP users?

I unfortunately do not have access to Windows, though I've been able  
to work with
some people who do.  However, the results seem unpredictable.  They  
tried stty'ing
different settings but with mixed results.  In most cases the users  
felt that
Windows TELNET was randomly sending a double return.

The only work around is for the user to escape back to the TELNET>  
prompt on the
Windows client and type 'unset crlf' and then continue.

Is there a modification that can be done to telnetd to make that  
unnecessary and
still accommodate non-Windows TELNET clients?

Again, yes, using TELNET across public networks is bad.  I agree, but  
that is not the
issue here.