Did you run iwfsck to check if there are any errors in the store before and after you deleted the files from the workflow store. I do agreed that deleting the workflow store and recreating the store is not the best way to delete couple of bad workflows.
Unless something has changed recently - iwfsck does not perform any consistancy checks on the workflow store - only the content store(s).
I was under the impression that iwfsck can be used for all the stores including the workflow store, but I might be wrong. Is there any other utility that used to check for errors in the workflow store? Thanks for correcting me about iwfsck CLT usage.