I have been the same situation, you negative keyword campaign until there is next to no traffic.
Broad match modifier helps, but still does not generate significant traffic.
I have tried display ads, not much luck there.
Still searching for a solution for these types of service/product clients.
The is a book about called [selling the invisible] that my wife told me about, it is on my short reading list.