Ciao,
purtroppo non so dirti come tentare di recuperare la cartella Documenti.
Una volta persi, e non ne conosco ancora il motivo, tutti i messaggi di Posta Inviata di Outlook Express, e senza aver fatto alcunché... Il file apposito s'era cancellato, e a tutt'oggi ne ignoro le ragioni.

Posso suggerirti di verificare se si sono liberati effettivamente 21 Gb di spazio sull'hard disk: per qualche oscuro motivo, la cartella potrebbe essersi spostata o rinominata... Voglio dire che sul Desktop c'è la cartella Documenti, ma in realtà è un collegamento. Clicca col destro del mouse, vedi Proprietà e controlla dove punta...

Per deframmentare io uso Auslogic Disk Defrag, velocissimo (deframmento una media di 45 Gb...), e poi mi dice che ci sono dei file da cancellare, ma per farlo occorre un altro programma da comprare... Può darsi che i programmi che hai usato effettuino questa cancellazione da soli, e si siano portati via la cartella Documenti.

Per la pulizia del registro, ti suggerisco Ccleaner (fa anche altro...) ed il micidiale Glary Utilities: micidiale perché trova voci di registro da cancellare che Ccleaner non trova.