Maybe try the following (Note the "~/" in the 'to' attribute)
<!-- start Intelligencia.UrlRewriter settings -->
<rewriter>
<!-- When changing these rewrites make sure that you sync them with rewriteUrlTemplate in the appSettings section. -->
<rewrite url="~/Product-(.+)_(\d+).aspx" to="~/product.aspx?pid=$2"/>
<rewrite url="~/Catalog-(.+)_(\d+).aspx$" to="~/catalog.aspx?cid=$2"/>
<rewrite url="~/Catalog-(.+)_(\d+).aspx\?(.+)" to="~/catalog.aspx?cid=$2&$3"/>
<rewrite url="~/Page-(.+)_(\d+).aspx" to="~/default.aspx?pageId=$2"/>
</rewriter>
<!-- end Intelligencia.UrlRewriter settings -->