I'm sorry to spoil the fun but I see the same problem on Lucid with the new package.

Only thing that might  be of interest is that this is a xen 4 guest.

More info and tests available on request.

root@somehost:/var/log >(zcat daemon.log.3.gz ; zcat daemon.log.2.gz ; cat daemon.log.1 ; cat daemon.log)|grep 'somehost init: ssh'|more
Jan 11 09:24:36 somehost init: ssh main process (3466) terminated with status 255
Jan 11 09:30:12 somehost init: ssh main process (3799) terminated with status 255
Jan 11 11:07:20 somehost init: ssh main process (3971) terminated with status 255
Jan 11 20:44:30 somehost init: ssh main process (369) terminated with status 255
Jan 11 21:54:04 somehost init: ssh main process (423) terminated with status 255
Jan 11 22:08:05 somehost init: ssh main process (1573) terminated with status 255
Jan 15 22:23:03 somehost init: ssh main process (1859) terminated with status 255
Jan 16 18:05:26 somehost init: ssh main process (400) terminated with status 255
Jan 23 20:04:04 somehost init: ssh main process (458) terminated with status 255
Jan 26 14:34:56 somehost init: ssh main process (4856) terminated with status 255
Jan 26 14:35:59 somehost init: ssh main process (21968) terminated with status 255
Jan 30 01:36:19 somehost init: ssh main process (396) terminated with status 255
Jan 30 13:48:46 somehost init: ssh main process (502) terminated with status 255
Jan 31 15:44:56 somehost init: ssh main process (419) terminated with status 255
Feb  2 12:01:33 somehost init: ssh main process (379) terminated with status 255
Feb  2 12:01:33 somehost init: ssh main process ended, respawning
Feb  2 12:01:33 somehost init: ssh main process (389) terminated with status 255
Feb  2 12:01:33 somehost init: ssh main process ended, respawning
Feb  2 12:01:33 somehost init: ssh main process (393) terminated with status 255
Feb  2 12:01:33 somehost init: ssh main process ended, respawning
Feb  2 12:01:33 somehost init: ssh main process (406) terminated with status 255
Feb  2 12:01:33 somehost init: ssh main process ended, respawning
Feb  2 12:01:33 somehost init: ssh main process (417) terminated with status 255
Feb  2 12:01:33 somehost init: ssh main process ended, respawning
Feb  2 12:01:33 somehost init: ssh main process (421) terminated with status 255
Feb  2 12:01:33 somehost init: ssh main process ended, respawning
Feb  2 12:01:33 somehost init: ssh main process (424) terminated with status 255
Feb  2 12:01:33 somehost init: ssh main process ended, respawning
Feb  2 12:01:33 somehost init: ssh main process (427) terminated with status 255
Feb  2 12:01:33 somehost init: ssh main process ended, respawning
Feb  2 12:01:33 somehost init: ssh main process (430) terminated with status 255
Feb  2 12:01:33 somehost init: ssh main process ended, respawning
Feb  2 12:01:33 somehost init: ssh main process (433) terminated with status 255
Feb  2 12:01:33 somehost init: ssh main process ended, respawning
Feb  2 12:01:33 somehost init: ssh main process (436) terminated with status 255
Feb  2 12:01:33 somehost init: ssh respawning too fast, stopped
Feb  2 16:39:02 somehost init: ssh main process (357) terminated with status 255
Feb  2 16:39:02 somehost init: ssh main process ended, respawning
Feb  2 16:39:02 somehost init: ssh main process (373) terminated with status 255
Feb  2 16:39:02 somehost init: ssh main process ended, respawning
Feb  2 18:27:19 somehost init: ssh main process (368) terminated with status 255
Feb  2 18:27:19 somehost init: ssh main process (414) terminated with status 255
root@somehost:/var/log >apt-cache policy openssh-server
openssh-server:
  Installed: 1:5.3p1-3ubuntu5
  Candidate: 1:5.3p1-3ubuntu5
  Version table:
 *** 1:5.3p1-3ubuntu5 0
        500 http://nl.archive.ubuntu.com/ubuntu/ lucid-updates/main Packages
        100 /var/lib/dpkg/status
     1:5.3p1-3ubuntu3 0
        500 http://nl.archive.ubuntu.com/ubuntu/ lucid/main Packages
root@somehost:/var/log >
root@somehost:/var/log >(last ; last -f wtmp.1)|grep '^reboot'
reboot   system boot  2.6.32-28-server Wed Feb  2 18:27 - 20:20  (01:53)    
reboot   system boot  2.6.32-28-server Wed Feb  2 16:39 - 18:26  (01:47)    
reboot   system boot  2.6.32-28-server Wed Feb  2 12:01 - 16:38  (04:36)    
reboot   system boot  2.6.32-28-server Mon Jan 31 14:42 - 20:20 (2+05:37)   
reboot   system boot  2.6.32-28-server Sun Jan 30 01:36 - 20:20 (3+18:44)   
reboot   system boot  2.6.32-28-server Thu Jan 27 14:13 - 00:15 (2+10:01)   
reboot   system boot  2.6.32-27-server Sun Jan 16 18:05 - 14:12 (10+20:07)  
reboot   system boot  2.6.32-27-server Sun Jan 16 16:57 - 18:04  (01:07)    
reboot   system boot  2.6.32-27-server Sun Jan 16 15:29 - 16:56  (01:27)    
reboot   system boot  2.6.32-27-server Sun Jan 16 09:46 - 15:29  (05:42)    
reboot   system boot  2.6.32-27-server Tue Jan 11 21:23 - 09:46 (4+12:22)   
root@somehost:/var/log >ls -altc /var/cache/apt/archives
.
.
.
-rw-r--r-- 1 root root   304198 2011-01-23 20:03 openssh-server_1%3a5.3p1-3ubuntu5_amd64.deb
.
.
.