I've also occassionally wanted to do a search and replace within
paragraph or character styles -- but there's no way to do this in
InDesign. It could be scripted though.
If you're brave, you can export to IDML, unzip the IDML, search-and-replace with a text editor, zip it back up, and import the IDML.