"When you run rescue you first need to mount all the partitions..."
No. You must run fsck against unmounted partitions. Do not use Knoppix for your rescue CD because it looks for partitions and tries to mount them. Use a rescue CD which does not try to mount partitions. Then run fsck -t (filesystemtype) /dev/hdxy against every partition but swap. Or if you use Knoppix then the first thing that you do in Knoppix is unmount all of your hard drive partitions.
"If you boot normally the partitions mount but the kernel does not seem to find where / is so it can not find /sbin/init to mount /dev/console. "
I think that one of your problems is that there are probably errors in / that need to be fixed with fsck before you can use / as a mounted file system.
"then do an update install of the old kernel, and finally update and patch the kernel with the latest version of the kernel and SSH patch."
You may or may not have to do these things after you run fsck.
"In order to use our backup I believe that we would still have to go throught this rescue procedure."
Yes. Probably. Actually if you are going to completely restore a partition then you should run mkfs and recreate the partition file system before you do the restore.
Be prepared. Create a LifeBoat CD.