Przypuszczam, że używasz silnika pamięci masowej, który obsługuje transakcje (np. InnoDB), ale nie wywołujesz db.commit() po USUŃ. Efekt DELETE jest odrzucany, jeśli nie dokonasz zatwierdzenia.
Zobacz http:// mysql-python.sourceforge.net/FAQ.html#my-data-disappeared-or-on-t-go-away :
Zobacz także to podobne pytanie SO:Kwerenda aktualizacji Pythona MySQLdb nie powiodła się
