Search for tags

Yes its very possible, you just need to create your own search form and processing function
form:

<form name="tag-search" method="POST" action="">
  <input type="text" vlaue="" name="tag-q" id="tag-q">
  <input type="submit" name="tag-submit" id="tag-submit" value="Search Tags">
</form>

processing:

<?php
if (isset($_POST['tag-submit']) && $_POST['tag-submit'] == "Search Tags" && isset($_POST['tag-q']) && $_POST['tag-q'] != ""){

    // @todo Sanity check and cleanup $_POST['tag-q'] here.

    $args = array('name__like' => $_POST['tag-q']);
    $tags = get_tags($args);
    $html="<div class="post_tags_search_r">";
    foreach ($tags as $tag){
        $tag_link = get_tag_link($tag->term_id);

        $html .= "<a href="https://wordpress.stackexchange.com/questions/13278/{$tag_link}" title="{$tag->name} Tag" class="{$tag->slug}">";
        $html .= "{$tag->name}</a>";
    }
    $html .= '</div>';
    echo $html;
}
?>

No this is something i have used in the past, the only downside to this is that name__like is case-insensitive so you might want to add the strtolower version to the name__like.