Does the space occupied by deleted rows get re-used?

It is paranoia :)

DB's don't grow in size unnecessarily, but for performance issues space is not freed either.

What you've heard most probably is that if you delete records that space is not given back to the Operating System. Instead, it's kept as an empty space for the DB to re-use afterwards.

This is because:

• DB needs to have some HD space to save its data; if it doesn't have any space, it reserves some empty space at first.
• When you insert a new row, a piece of that space is used.
• When you run out of free space, a new block is reserved, and so on.
• Now, when you delete some rows, in order to prevent reserving more and more blocks, its space is kept free but never given back to the Operating System, so you can use it again later without any need of reserving new blocks.

As you can see, space is re-used, but never given back. That's the key point to your question.

in innodb, there is no practical way of freeing up the space.

• use per table ibdata file, that willenable you to delete record copy thedata to a new table and delete oldtable, thus recovering records.
• use mysqldump and whole lots ofreceipe to clean up the wholeserver. Check following:
  http://dev.mysql.com/doc/refman/5.0/en/adding-and-removing.html

All of these methods become impractical when you are using huge tables(in my case they are more than 250GB) and you must keep them deleting records to better performance.

You will have to seriously think, whether you have enough space on your harddisk to perform one of the above function (in my case I do not think 1TB is enough for all these actions)

with Innotab table (and mysql itself) the option are fairly limited if have serious database size.