What is your TERM when you telnet?
This is the behavior I have always seen from vi on solaris.

> I have a telnetd on a NetBSD 3.0_BETA system with source dated from Jun 1=
5
> 2005.
>=20
> Using the telnet client from a NetBSD 2.0_STABLE system inside an xterm
> results in broken cursor keys inside vi. Instead of moving the cursor the=
y
> start insert mode and insert a letter (A, B, C, D for up, down, right,
> left) and a new line.
>=20
> Anything else seems the be fine. Cursor keys are working at the shell, in
> more etc. I have a tset line in my .profile, it has selected xterm as ter=
m
> type.
>=20
> When telnetting from the same box, but in a wscons console, to the same
> account I get vt220 as term type and all including vi is fine. When using
> vi locally on that machine it also works. From a different machine I get
> ansi term type and also everything is fine.
>