The recovery console doesn't depend on System Restore. As long as you have a real Windows CD rather than some manufacturer's recovery CD it should work.