お使いの Url Rewrite Module というのは IIS7.x 用に Microsoft が提供しているもの、即ち以下のページで紹介されているものだと思いますが、それを使って質問者さんと同様な設定にして検証してみました。
Tip/Trick：URL書き換え拡張の使用による一般的なSEO問題の修正
http://www.atmarkit.co.jp/fdotnet/scottgublog/20100430urlrewrite/urlrewrite.html
結果、質問者さんが書かれているような問題は全くなかったです。
開発環境は Vista Ultimate SP2 32-bit, IIS7（アプリケーションプールは ASP.NET v4.0 で統合パイプラインモード）, ASP.NET 4, requestEncoding は未設定（デフォルトで UTF-8）で、使用したブラウザは IE9 です。
同じ Url Rewrite Module をお使いだとすると、どこかのファイルが壊れているとか、質問者さん固有の問題かもしれません。
検証結果詳細を以下に書いておきます。
書き換えルール
--------------
<rewrite>
<rules>
<rule name="Japanese Query String Test">
<match url="dir/(.+)$" />
<action type="Rewrite" url="0024-QueryString.aspx?n={R:1}" />
</rule>
</rules>
</rewrite>
IE9 のアドレスバーに直打ちした URL
----------------------------------
http://aspnet4site/dir/あ
Fiddler2 による上記要求のキャプチャ結果
---------------------------------------
GET http://aspnet4site/dir/%E3%81%82 HTTP/1.1
Accept: text/html, application/xhtml+xml, */*
Accept-Language: ja-JP,en-US;q=0.7,fr-FR;q=0.3
User-Agent: Mozilla/5.0 (compatible; MSIE 9.0; Windows NT 6.0; Trident/5.0)
Accept-Encoding: gzip, deflate
Connection: Keep-Alive
Host: aspnet4site
Cookie: ASP.NET_SessionId=4z1ylkfmck32f2qgoo4tt4b3
IE9 に表示された応答
--------------------
X-Original-URL: /dir/%E3%81%82
あ[E3][81][82]
Request.Url.ToString(): http://aspnet4site/0024-QueryString.aspx?n=あ
Request.RawUrl: /dir/あ
Request.QueryString["n"]: あ
検証に使った 0024-QueryString.aspx のソース
-------------------------------------------
<%@ Page Language="C#" %>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<script runat="server">
protected void Page_Load(object sender, EventArgs e)
{
NameValueCollection headers = Request.Headers;
string[] keys = headers.AllKeys;
for (int i = 0; i < keys.Length; i++)
{
if (keys[i] == "X-Original-URL")
{
string[] values = headers.GetValues(keys[i]);
Response.Write("X-Original-URL: " + Server.HtmlEncode(values[0]) + "<br />");
}
}
string s = Request.QueryString["n"];
if (s != null)
{
Response.Write(s);
byte[] b = System.Text.Encoding.UTF8.GetBytes(s);
for (int i = 0; i < b.Length; i++)
{
Response.Write(string.Format("[{0:X2}]", b[i]));
}
}
Label1.Text = "Request.Url.ToString(): " + Request.Url.ToString();
Label2.Text = "Request.RawUrl: " + Request.RawUrl;
Label3.Text = "Request.QueryString[\"n\"]: " + Request.QueryString["n"];
}
</script>
<html xmlns="http://www.w3.org/1999/xhtml">
<head runat="server">
<title></title>
</head>
<body>
<form id="form1" runat="server">
<div>
<asp:Label ID="Label1" runat="server"></asp:Label>
<br />
<asp:Label ID="Label2" runat="server"></asp:Label>
<br />
<asp:Label ID="Label3" runat="server"></asp:Label>
</div>
</form>
</body>
</html>
