Maybe you should use native NGG tag engine instead of third-party search?
To do this, I created a new page with [tagcloud] tag on it, then in code, you listed abode I changed URL of created link from <?php bloginfo('url'); ?>/?s=<?php echo $tag->slug; ?> to <?php bloginfo('url'); ?>/nggallery/page-275/tags/<?php echo $tag->slug; ?> where 275 is an ID of page with tagcloud. Worked for me (but i still have problem with non-english tag names, baw).
