Mysql Overhead problem

One of my tables in my database often comes up with the Overhead XX bytes (in red) in phpmyadmin. Usually 20-120 bytes

I know using OPTIMIZE table_name will clear it and from what I can gather from the google info I found it's from deleting within the table.
This tables contents aren't delete though, just always updated

Anyway around having to optimize the table all the time, happens every couple of days and short of running an "OPTIMIZE table_name" in the cron job after the (what I think is) the cause, I have no idea what to do.

If I leave it for a while the bytes build up and if I try optimize the table can hang with the 'in_use' message and need to repair it before anything will work again (pooped my pants first time that happened)

In some ways I'm hoping it's a coding fault, some code I can change.
I used the EXPLAIN SELECT ... a lot to try optimize the tables (maybe thats my problem)

The table has 1283 rows, 1 primary, 2 indexes, row size is 47 bytes and total is 60,224 Bytes

cat_id <-- primary/indexed, never changes
cat_name <-- never changes
parent_id <-- indexed, never changes
deleted <-- never changed to date
counter <-- often changes
sub_counter <-- often changes