Pérdida de espacio.

Falso.

Primeramente desmentirte totalmente el tema de que cada vez que se formatea se pierde 1Gb. Bufff! Mi disco duro de 40Gb debería haberse agotado hace mucho tiempo.
Ese espacio que dices que falta, se lo reserva el mismo disco duro para su organización de datos y estructura. No podrás recuperarlo porque es así. Cuanto más grande es el disco duro, más Gigas de diferencia verás entre la capacidad real y la que te deja utilizar.
Pero vamos, que no es problema del disco duro ni de Sistemas Operativos.
Como mucho, podrás recuperar unos poco megas si eliminas todas las particiones y las vuelves a crear, ya que el Linux, al igual que el XP, se reservan una partición oculta de 8Mb. Será lo poco que puedas recuperar. Como ves, prácticamente nada.

Al formatear siempre se pierde espacio, es una trampilla comercial, el fabricante dice 80 gb, porque redondea ya que se basa en dividir por 10000, pero en realidad se ha de dicidir entre 1024, así 80/1024= 0.0078, es decir en realidad tiene unso 78 gb.
En tu caso al tener windows y linux, el gector de arranque se lleva lo suyo, el lilo, este podría ser el motivo, pero una vez no solo formateado, sino también eliminada las particiones, esto desaparece, si no quieres eliminar las particiones, ese espacio continuara.
Te pongo un enlace a un programa que te indicara cuanto espacio ocupa cada carpeta del disco, así sabrás cual esta ocupando ese espacio: ( es gratuito)
http://spacemonger.softonic.com/ie/25128

Para empezar dejame decirte que lo que te mencionaros es una completa mentira si lo formateas de la forma ordinaroia te recomiendo que utilices el sistema de comandos del viejpo msdos y para ser más especifico el comando "FDISC" para que quites todas particiones hechas antes durante y después de lo que le desinstaleste o instalaste o ya si quiere hacer una formateo total formatea tu disco a bajo nivel.