How to handle special characters in web.config rew

I'm getting errors on my rewrite rules when the URL contains a special character:

This URL http://www.example.com/bungalow/rent/state/texas/street/exloër/exloër with this rewrite rule:

    <rule name="rentals by proptype+state+city+street">
      <match url="^([a-zA-Z0-9-+]+)/rent/state/([a-zA-Z-+]+)/street/([a-zA-Zë-+]+)/([0-9a-zA-Zë-+']+)$" />
      <action type="Rewrite" url="search_new.aspx?proptype={R:1}&amp;state={R:2}&amp;city={R:3}&amp;street={R:4}" />
    </rule>

results in a 500 error

This URL http://www.example.com/bungalow/rent/state/texas/street/exloër/exloër with this rewrite rule:

    <rule name="rentals by proptype+state+city+street">
      <match url="^([a-zA-Z0-9-+]+)/rent/state/([a-zA-Z-+]+)/street/([a-zA-Z-+]+)/([0-9a-zA-Z-+']+)$" />
      <action type="Rewrite" url="search_new.aspx?proptype={R:1}&amp;state={R:2}&amp;city={R:3}&amp;street={R:4}" />
    </rule>

results in a 404 error

How can I handle special characters in the rewrite rule?

update 1

The URL in question is displayed with a ë character, but when I copy the address, it's escaped to this %c3%abr With this rule I still get a 404 error:

    <rule name="rentals by proptype+state+city+street">
      <match url="^([a-zA-Z0-9-+]+)/rent/state/([a-zA-Z-+]+)/street/([a-zA-Z%-+]+)/([0-9a-zA-Z%-+']+)$" />
      <action type="Rewrite" url="search_new.aspx?proptype={R:1}&amp;state={R:2}&amp;city={R:3}&amp;street={R:4}" />
    </rule>

So I guess the real question would be, how to handle % characters in the rewrite rule?

Your last attempt had almost correct regex, you just had one small mistake (forgot to add 0-9 to third block). Correct regexp is:

^([a-zA-Z0-9-+]+)/rent/state/([a-zA-Z-+]+)/street/([a-zA-Z0-9%-+]+)/([0-9a-zA-Z%-+']+)$

But in rewrite rule you need to use variable {UNENCODED_URL}.

Working example is:

<rule name="rentals by proptype+state+city+street" stopProcessing="true">
    <match url=".*" />
    <conditions>
        <add input="{UNENCODED_URL}" pattern="^/([a-zA-Z0-9-+]+)/rent/state/([a-zA-Z-+]+)/street/([a-zA-Z0-9%-+]+)/([0-9a-zA-Z%-+']+)$" />
    </conditions>
    <action type="Rewrite" url="search_new.aspx?proptype={C:1}&amp;state={C:2}&amp;city={C:3}&amp;street={C:4}" />
</rule>

UPD

After example from comments:

Your url: http://www.example.com/bungalow/rent/state/north-dakota/stre‌‌et/savanah/%27s-gr‌ac‌eland has some hidden special characters (even SO can't parse it properly). You can check how it's encoded here: https://www.urlencoder.org/.

Becased on that i changed the regexp in the rule with following:

<rule name="rentals by proptype+state+city+street" stopProcessing="true">
    <match url=".*" />
    <conditions>
        <add input="{UNENCODED_URL}" pattern="^/([a-zA-Z0-9\-+]+)/rent/state/([a-zA-Z\-+]+)/([a-zA-Z0-9%\-+]+)/([a-zA-Z0-9%\-+]+)/([0-9a-zA-Z%\-+']+)$" />
    </conditions>
    <action type="Rewrite" url="search_new.aspx?proptype={C:1}&amp;state={C:2}&amp;city={C:4}&amp;street={C:5}" />
</rule>