Why doesn't the function taxonomy_term_search exists?
Long story short, it does not exist because either no one wrote it, or maintainers found it not suited for inclusion in taxonomy.module for whatever reasons. For most purposes, taxonomy_get_term_by_name is enough. When it's not, there are various search solutions in separate, search oriented modules.

If you think you can write it, and make it good, please do so, and then post entry in issue queue with appropriate patch file.