On a related note, here is a comparison of nmap against a Linux 
2.6.9-gentoo-r1 machine and a NetBSD 2.0rc4 machine both running OpenSSH 
on port 4222.

# nmap -O -sV -v -p4100-4300 -T5 dirk

Starting nmap 3.75 ( http://www.insecure.org/nmap/ ) at 2004-11-13 20:22 EST
<you all know this part>
PORT     STATE SERVICE VERSION
4222/tcp open  ssh     OpenSSH 3.8.1p1 (protocol 2.0)
MAC Address: 00:10:B5:12:EA:FA (Accton Technology)
Device type: general purpose
Running: Linux 2.4.X|2.5.X|2.6.X
OS details: Linux 2.4.18 - 2.6.7
Uptime 0.240 days (since Sat Nov 13 14:36:34 2004)
TCP Sequence Prediction: Class=random positive increments
                         Difficulty=4079068 (Good luck!)
IPID Sequence Generation: All zeros

Nmap run completed -- 1 IP address (1 host up) scanned in 2.115 seconds

Versus:

# nmap -O -sV -v -p4100-4300 -T5 odin

Starting nmap 3.75 ( http://www.insecure.org/nmap/ ) at 2004-11-13 20:22 EST
<you all know this part>
PORT     STATE SERVICE VERSION
4222/tcp open  ssh     OpenSSH 3.6.1 (protocol 1.99)
MAC Address: 00:06:5B:01:C1:05 (Dell Computer)
Device type: general purpose
Running: NetBSD
OS details: netbsd 1.6ZH - 2.0RC4
TCP Sequence Prediction: Class=random positive increments
                         Difficulty=10365408 (Good luck!)
IPID Sequence Generation: Incremental

Nmap run completed -- 1 IP address (1 host up) scanned in 3.072 seconds

NetBSD is a clear winner of course, but it still found the OS pretty 
accurately. On another note, it's an interesting thing that the NetBSD 
box took longer to scan, even though it's much faster and under less 
load. Even scanning localhost on NetBSD takes a long long time, but 
under Linux it's instant (possibly an nmap hack since I doubt NetBSD is 
slow at loopback sockets)

I don't have a FreeBSD box available to comment on, but in all of my 
previous investigations it was not identifiable and the Difficulty was 
maximal (all 9's). IPID had something good to say but I forgot what. 
This is a Damn Good Thing. I can only assume OpenBSD behaves the same 
way if not better.

Another idea could also be to import the new OpenSSH. Looks like 
NetBSD's base package is behind in this regard. OpenBSD put in some new 
features in the latest release which could be handy.