I know this is a very old topic/problem description but maybe a new approach can be performed.
I had the same issue with an InnoDB Engine table.
As "sdesvergez" said, the optmize works dispite the returned message saying otherwise. But we don't know what are the real consequences are in the background.
I am assuming your table is not too big (less than 1GB) like mine (200Mb).
I made a change in the table structure, instead of "pure" InnoDB I set the table with a single partition:
CREATE TABLE IF NOT EXISTS <<schema>>.<<table name>>(
<<your tabe definition>>
) PARTITION BY KEY(<<key from table, in my case I used "day">>)
PARTITIONS 1;
The table still works with the InnoDB engine, but it now has a deeper structure with the Partitions.
After you do so, you can can then rebuild the partition in order to optimize it.
The rebuild will lose the space allocated to the deleted records and also optimize the table. In my case this process took 10 seconds.
This way you don't get any strange messages in the status of the operation.
So far I have not had any data loss or any other problems using this method, but a very fast and organized table.