Is Enabling Double Escaping Dangerous?

I would just like to add some information to Eamon Nerbonne's answer related to the "what to do" part of your question (not explaining the whys).
You can easily change a particular application's settings too with

1. opening the console with admin rights (Start - cmd - right click, Run as administrator)

2. typing in the following (taken from here: http://blogs.iis.net/thomad/archive/2007/12/17/iis7-rejecting-urls-containing.aspx):

   %windir%\system32\inetsrv\appcmd set config "YOURSITENAME" -section:system.webServer/security/requestfiltering -allowDoubleEscaping:true
   

   (you can e.g. substitute YOURSITENAME with Default Web Site for applying this rule to the default website)

3. Enter, ready.

An example:

1. firstly I had the same problem:
2. Typing in the text mentioned above:
3. Now it works as expected:

Edit: Added emphasis to relevant sections.

Basically: IIS is being excessively paranoid. You can safely disable this check if you're not doing anything particularly unwise with the uri decoded data (such as generating local filesystem URI's via string concatenation).

To disable the check do the following (from here): (see my comment below for what double escaping entails).

<system.webServer>
    <security>
        <requestFiltering allowDoubleEscaping="true"/>
    </security>
</system.webServer>

If the plus symbol is a valid character in a search input, you will need to enable "allowDoubleEscaping" to permit IIS to process such input from the URI's path.

Finally, a very simple, if limited workaround is simply to avoid '+' and use '%20' instead. In any case, using the '+' symbol to encode a space is not valid url encoding, but specific to a limited set of protocols and probably widely supported for backwards-compatibility reasons. If only for canonicalization purposes, you're better off encoding spaces as '%20' anyhow; and this nicely sidesteps the IIS7 issue (which can still crop up for other sequences, such as %25ab.)

Have you thought about having the search URL like '/search/a/b/c'?

You'd need to setup a route like

search/{*path}

And then extract the search values from your path string in the action.