Yo he dejado mi PS3 varias veces como si fuese de fábrica usando la opción de restablecer sistema PS3, dejándola limpia como una patena. No me ha hecho falta entrar en el menú recovery ni nada. Una vez se restablezca, te pide reiniciar, y lo primero que sale una vez reiniciada es lo de enchufar un mando por USB y darle al botón PS, como la primera vez. Cuando ya haces la primera configuración, el PSNetwork no tiene ningún dato tuyo, eso sí, al menos esto es así con el firmware 3.10, no sé si con anteriores también.
Edito: Recuerda que si vas a usar tu cuenta PSNetwork en otra PS3 (porque te la cambias a una slim o lo que sea) y sobre todo si tienes contenido comprado, desactiva la consola tanto para juegos como para vídeo para no perder uno de los 5 slots que tenemos por cada cuenta.