You can telnet to a windows box if there's a telnet server on that box. Windows doesn't provide one by default until... XP, perhaps; at older versions, I have customers who have used third party telnet packages like Georgia Softworks to enable telnet onto Windows servers.
Removing telnet feels a whole lot like saying I'm going to remove notepad to prevent people from editing files. There are other ways that they can do it, and frankly, all it does it make my own life a little more difficult. You still have rlogin, ssh, rsh, and at least a couple of other methods for getting into that Linux box that are available. All you've done is made sure that anyone who gets in will have to be a sophisticated hacker, not a simple one. IOW, common hoodlums are not allowed; you must be mafioso or yakuza to get in.
That being said, what are you trying to protect your Linux box from? If it's on your LAN, and your LAN is properly secured, you're protecting yourself from... yourself.
If it's exposed to the internet, then there are many more important things besides telnet that you need to worry about.
BTW, Samba can leave you with an even bigger hole than telnet. If you're not requiring passwords for the shares, then you're even worse off.