When you say keyword, do you mean term?
I just did a quick test to confirm: I can have the same term, which has the same slug, in both the Category and Post Tag taxonomies, so I assume that custom taxonomies likewise can have terms with the same slug.
So, might there be some taxonomy/term confusion happening here? The search?tax=foo seems to imply a search based on a taxonomy, rather than on a taxonomy term. A taxonomy term search would look like search?taxonomy=foo&term=bar, or perhaps search?term=bar.