I am running freebsd on virtualbox (with virtualbox-ose-additions installed in freebsd).
the vim startup is very quick (instantaneous) in the vbox console window.
but when connected via putty from the host machine, the vim takes about 6-7 seconds to startup.
the connection from putty is via ssh authentication.
and the host to vbox connection is NAT+portforwarding.
This has happened to me when I had X11 Forwarding
turned on in Putty but didn't have an X Server running (always the case when using Putty from (I assume) Windows unless you're running specific software like Cygwin or Xming to have a local X Server).
Alternately, your shell startup scripts may set the DISPLAY
environment variable improperly when you're ssh'd in instead of using a console.