Damn, this was a tricky one – a bit of coding, a sprinkle of XAML and here it is. And it works. You can set this Behavior to any TextBox and turn it into Windows 7 search box like thingy. You can define your own Search and Clear icons (ImageSource) and (if you don’t want search-as-you-type) Search command (ICommand). The good thing is that it doesn’t affect the style/template you set for the TextBox, as it is implemented as Adorner.
Download here (rename .DOC to .RAR – wordpress limitation).