Mavericks - ssh to host under search domain
Have you tried to SSH to the IP address? It may be simple enough to work. Take the DNS out of the picture if you have the IP addresses of the hosts.
Whenever I use SSH out of Terminal I have always used the IP address and never had any issues.
For reference - this is exactly what I was looking for: http://www.eigenspace.org/2011/07/fixing-osx-lion-dns-search-domains/