ON DELETE CASCADE pseudo delete
Perhaps you should look into using tombstone tables.

Here is what I mean: Suppose you had this table

CREATE TABLE mytable
(
    id INT NOT NULL AUTO_INCREMENT,
    ... other columns ....
    PRIMARY KEY (id),
    ... other indexes ...
);


Now, create a table with the IDs that are marked for deletion

CREATE TABLE mytable_deleted
(
    id INT NOT NULL,
    PRIMARY KEY (id)
);


So instead of doing

DELETE FROM mytable WHERE MOD(id,100) = 0;


You would add the ids to mytable_deleted

INSERT IGNORE INTO mytable_deleted
SELECT id FROM mytable WHERE MOD(id,100) = 0;


From here, you simply have to add the mytable_delete to all queries

To see all rows

SELECT * FROM mytable;


To see non-deleted rows

SELECT * FROM mytable A LEFT JOIN mytable_deleted B USING (id) WHERE B.id IS NULL;


To see deleted rows

SELECT * FROM mytable A LEFT JOIN mytable_deleted B USING (id) WHERE B.id IS NOT NULL;


or

SELECT * FROM mytable A INNER JOIN mytable_deleted B USING (id);


To perform the actual deletion

DELETE A.* FROM mytable A INNER JOIN mytable_deleted B USING (id);
TRUNCATE TABLE mytable_deleted;


CAVEAT

This will means that lots of SELECT queries must incorporate the tombstone table.

I have discussed this before : Tombstone Table vs Deleted Flag in database syncronization &amp; soft-delete scenarios. You should read the accepted answer from Leigh Riffel instead of mine for a more honest critique as to which method is better in your case.