Are you sure you tried to repair the correct table?
Anyway...possible that you've got more than 1 table with an error. If you or your host really cannot repair those 2 indicated, then here's a worst-case scenario method to resolve...
Backup your database
Go into the ACP and turn your site offline
Using PHPMyAdmin (or whatever you want) rename the following 2 tables core_search_index_tags and core_search_index to whatever you want (I'd just put _old on the end)
Back to the ACP, go to the support page - you've end up with a 'Database problems' indicator, so click the 'Fix This' button
Run the provided scripts against your database - either 'Fix automatically' or manually copy them out to run them elsewhere.
Once verified as done, go to admin/?app=core&module=discovery&controller=search and click on 'Rebuild search index'