Very strange that something so fundamental would not be working. Just off the top of my head, what I'd check...
- Have you logged your database queries and confirmed that there is a DELETE SQL statement?
- Are you using a database transaction and not committing it?
- Stupid question, it's got to be asked... you are looking at the correct database and the correct table?