You are correct that, within the partitioning handler, it will need to move the row from one partition to the other, which is done by an insert into the new partition and a delete from the old partition internally.
But since you have PRIMARY KEY (id) you cannot partition by 'deleted', the primary key must include all columns in the partitioning function:
If you use MySQL 5.5's new features COLUMNS partitioning and TRUNCATE PARTITION, you could try something like:
CREATE TABLE `responses` (
`id` int(10) unsigned NOT NULL AUTO_INCREMENT,
`other_id` int(11) NOT NULL,
`deleted` tinyint(1) NOT NULL DEFAULT '0',
PRIMARY KEY (`id`,`deleted`)
PARTITION BY RANGE COLUMNS(deleted,id)
(PARTITION pActive VALUES LESS THAN (1,0),
PARTITION pDeleted VALUES LESS THAN (MAXVALUE,MAXVALUE))
And use ALTER TABLE responses TRUNCATE PARTITION pDeleted, to finally remove the deleted rows.
If your idea is to always mark rows as deleted and as some kind of maintenance, export/archive/delete the marked rows. Then using partitioning would give you a much faster operation (since you can use DROP PARTITION or TRUNCATE PARTITION, which is very fast operations, note however that they differ in transactional behavior from an ordinary delete, since they cannot be rolled back). But it could be at the expense of the update of the deleted column. But you have to benchmark this your self since it depends on the engine you use etc (I don't think it would be that big penalty).
In the development branch for MySQL (5.6) we have added the possibility to EXCHANGE PARTITION WITH TABLE which would match your archive step very good:
So if you plan to do mark rows as deleted even without partitioning, I would suggest you to try partitioning! This way you should get much faster 'Delete all marked rows' operation.