Al no ser que tengas datos que no quieras que sean recuperados por otras personas puedes hacer un formateo rápido ("format /q" desde la línea de comandos). Sólo borra las entradas de los archivos y directorios y no los datos en sí que estos contienen. Es mucho más rápido y no afecta tanto al disco duro. (aún así para poder cargarte un disco duro a base de formateos puros y duros tendrías que formatearlo varios cientos de veces, como poco).
Si optas por borrar Windows (la solución de "yocutus") acuerdate de borrar la carpeta de Windows (Windows o WINNT, el primero para 9x y ME y el segúndo para NT, 2k y XP), la carpeta "Archivos de programa" y si usas un Windows de la serie NT (NT, 2k o XP) casi que me cargaría también "Documents and Settings" (guardando primero "Mis documentos" de cada usuario).