Ho anche avuto lo stesso problema in Mac OS X Mountain Lion o Lion.
Prima di tutto, la tua domanda principale è vera: Time Machine dovrebbe rimuovere i vecchi backup quando il disco è pieno, e questo è uno strano comportamento che stai avendo.
Ciò che ha risolto il mio problema era semplicemente il ripristino delle preferenze di Time Machine rimuovendo il file
/Library/Preferences/com.apple.TimeMachine.plist
Quando lo fai, Mac OS dimenticherà il tuo disco e quando lo ricollegerai ti chiederà "vuoi usare questo disco come Time Machine?". Ho detto di sì e ho avviato un nuovo backup, che è andato bene.
Inoltre, spero che tu non stia rimuovendo vecchi backup semplicemente distruggendo le cartelle dal Finder: per rimuovere manualmente i vecchi backup devi inserire Time Machine, selezionare il backup che vuoi rimuovere e fare clic sull'icona a forma di ingranaggio e quindi selezionare Rimuovi backup. Se hai semplicemente spostato vecchi backup nel Cestino, non è un buon modo per andare: probabilmente hai corrotto parte dell'indicizzazione interna nella Time Machine (ed è forse per questo che chiede più dati). Per quanto ne so, non c'è cura per l'altro che cancellare il disco e avviare nuovamente una nuova macchina del tempo.