Immagino che tu stia utilizzando un motore di archiviazione che supporta le transazioni (ad es. InnoDB) ma non chiami db.commit() dopo il DELETE. L'effetto del DELETE viene scartato se non esegui il commit.
Vedi http:// mysql-python.sourceforge.net/FAQ.html#my-data-disappeared-or-won-t-go-away :
Vedi anche questa domanda SO simile:La query di aggiornamento Python MySQLdb non riesce
