Pagination not working with advanced search

Question

I'm building a site which uses custom post types almost exclusively. I therefore wrote a custom loop for them which meant I hit the issue of pagination not working. With a bit of searching I found the following code.

            <?php
              if ($paged > 1) { ?>
                <a href="<?php echo '?paged=' . ($paged -1); ?>">&larr;</a>
                                <?php }
            for($i=1;$i<=$loop->max_num_pages;$i++){?>
                <a href="<?php echo '?paged=' . $i; ?>" <?php echo ($paged==$i)? 'class="selected"':'';?>><?php echo $i;?></a>
                <?php
            }
            if($paged < $loop->max_num_pages){?>
                <a href="<?php echo '?paged=' . ($paged + 1); ?>">&rarr;</a>
            <?php } ?>

Unfortunately this isn't working with the search function I've written which overwrites the loop when a user selects custom taxonomies from a dropdown list. This can be seen in action at http://www.findabuilder247.com/directory (do a search for Carpenter in Coventry)

The pagination displays indicating that there are more profiles to be seen however the pagination code I've got simply takes you to the second page of the directory and not the search results. I though this may have been because I'm using $_GET and not $_POST however that made no difference.