Not enough space for MySQL optimize; do new rows overwrite existing data?
There is a user comment on the OPTIMIZE TABLE documentation page that had the same situation as you. His solution was to copy the table somewhere else, optimize, then copy back. This required offline time.
Unfortunately, my solution would also require offline time as well, for 70GB worth of data. Something like this:

mysqldump table from another machine with enough space
DROP TABLE foo
Load table from the mysqldump file: mysql -hXXX.XX.XX.XXX -u... -p... &lt; foo.sql

The downtime will be from the DROP TABLE step until the load table from a remote host of 70GB of data can be completed.
One potential bright spot is that new INSERTS will re-use the space created from DELETES:

Deleted rows are maintained in a linked list and subsequent INSERT operations reuse old row positions.

But this is what causes fragmentation to begin with. So you will need to make sure your tablespace is optimized frequently to prevent this in the future.
I just want to throw out there that to run an optimize query, you're always going to need at least the database size + the size of the table you're optimizing available on disk.
As an example, this means for a database size of 30GB and the table your optimizing is 28GB, you will need at minimum a harddrive that can fit 58GB of data space. This is because MySQL rewrites a new temporary file and then replaces the old one.
I say at least, because there's always other things going on. You'll need space for other programs, MySQL might be creating on-disk temporary tables during the operation, etc.