Hi!
I know what you mean, but it’s not yet possible in wordpress. The wordpress engine is not capable of returning non-post objects as results.
However I see your theme has a function implemented to list the “stores” cupons on a specific url, which is something that might make this possible in your case. I have changed the “Redirect url” option on the General Options->Behaviour panel to “?store={phrase}”. So it now redirects to the store page coupon search. This is the closest way for now.
I’m in contact with a few wordpress core developers, and hopefully the taxonomy search is going to be available as a core feature in wordpress from version 4.5. Let’s hope so. Many, many people have requested this from them.