Google turned up some hints about the Regex search, but no apparent solutions. After playing around a bit with the regex search in Visual studio, I found that it supports multiline text in both the search and replace strings.
When you're using "Find and Replace" in Visual Studio you can enable Regular Expressions, under "Find options", as shown in the screenshot. The regular expressions let you represent newlines in the search or replace fields, by using a \n. Cool! I've included an example below the image.
But beware, when you enable regular expressions you need to escape special characters, in my case < and >, with a backslash. Your "Find" statement will be interpreted as a regular expression. Check out the MSDN page on regular expressions in Visual Studio to learn more about which characters are special and which are not.
Update Sep. 2012: This post deals with Visual Studio 2010. Regular expressions have changed in VS 2012, as you'll see from the link above. See the comments on this post for a new example of multiline search and replace for both VS 2010 and VS 2012.
In my case, I wanted to add a new module directly after the WIF SessionAuthenticationModule. I've shortened the config lines, for space and readability. To match the config line I had to escape < and > which have special meaning in a regex.\<add name="SessionAuthenticationModule" ... PublicKeyToken=31bf3856ad364e35" /\>
And you want to replace it with itself, followed by a new line of config (the \N represents the newline):