Non so per mysql ma per DB2/400 i record cancellati di una tabella non lo sono davvero finché non si riorganizzi la tabella.
Con l'app ad-hoc è possibile poi ripristinare uno o più records. Forse esiste la stessa cosa per mysql.