As you mentioned you're over your database and it's not letting you optimize it.

Ask your host to either:

Increase your MySQL space temporary (permanently if you pay extra, maybe) so you correct it.

or have him do it:

Example: Could you please goto my database "name here" and "Repair" and then "Optimize" it for me, it's too large and I'm hoping this will correct my issuse.

or consider yourself finding a new host.