Recover the disk space after deleting rows from table
You will have to take the table offline to prevent any reads or writes that would get locked  and probably have to roll back. If the table is called mydb.mytable, here is what you must do:
USE mydb
DROP TABLE IF EXISTS mytablenew;
CREATE TABLE mytablenew LIKE mytable;
ALTER TABLE mytable RENAME mytableold;
INSERT INTO mytablenew SELECT * FROM mytableold;
ANALYZE TABLE mytablenew;
ALTER TABLE mytablenew RENAME mytable;
DROP TABLE mytableold;

Any queries attempting to read from or write to mytable will fail immediately rather than hang on a lock from OPTIMIZE TABLE.
Give it a Try !!!
UPDATE 2013-08-26 15:24 EDT
Look back at the code I suggested. Please note the line
ALTER TABLE mytable RENAME mytableold;

That line takes the table offline with respect to the application.
To get a good idea how long it should take to optimize run the following:
USE mydb
CREATE TABLE mytablenew LIKE mytable;
INSERT INTO mytablenew SELECT * FROM mytable;

However long this takes, is how long it will actually take to run.