How can I search the windows registry with regular expressions?

You can use PowerShell with -match:

dir HKCU:\ -rec -ea SilentlyContinue |   

ForEach-Object {   
       if((get-itemproperty -Path $_.PsPath) -match "\wSomestring\w")  
    {   
          $_.PsPath
    }   
} 

This will search the HKEY_CURRENT_USER hive.

The free RegAlyzer utility searches by substring, wildcard (*,?), boolean (AND OR NOT), and regular expression:

RegAlyzer is a tool to browse and change the registry. It was created because of a few features we missed in the original regedit tool, from support for exotic value types over background and regular expression search to better bookmarks, displaying .reg files in the accustomed style and a history view.

If it's just a matter of searching it without changing anything (no Search & Replace), export the whole registry to a .reg file and use your favorite text editor that supports regular expressions (Notepad++, Textpad, PSPad, ...).

To export the whole registry, right-click the Computer node in Registry Editor and select Export.

Watch out, the exported file can be huge. I just tried and the file was 250 MB big.

Encoding update: On WinXP, cygwin's file utility reports the exported data as Unicode text, UTF-16, little-endian.