Now, if it's going to do this, perhaps it should kill off the *most*
   recent process, as the *least* recent process is the one most in need
   of the swap space.

netbsd doesn't do this.
   
   Has anyone run out of swap yet?

yes.  the machine just stops.  well, it gets _VERY_ slow.

.mrg.