Is it a bad design decision to use links that are gray instead of blue for titles in search results in order to fit with the rest of the site's color scheme? What about ones that only underline when you mouse over them?
If you want people to click on links they should stand out. That's the only real rule. Blue and underlined is not the only way to go and if for example your text was blue those links would not stand out.
Underlining on mouseover is fine, but it detracts from the ability of your links to stand out - I'd suggest balancing that by giving them a good contrasting color, and possibly making them bold as well.
The problem is that most people are used to blue links to indicate clickability, and use this information subconsciously. If you make the links gray, you have to train users to click on those, and it's yet another barrier to actions/clicks/conversion.
Underlining on mouseover is fine, but it detracts from the ability of your links to stand out - I'd suggest balancing that by giving them a good contrasting color, and possibly making them bold as well.