After some prompting by Behaviour, I finally took a second stab at writing a fix for this styling mess.
The tricky bit here is that the "practically indistinguishable" link colors shown in search are actually the default link colors for the site, so changing them has all sorts of unexpected side effects. Some of those are good (there are other places, besides search, where it would be nice to be able to tell visited and unvisited links apart), but some interact in funny ways with other CSS rules in the math.SE style sheet.
In particular, a fairly reasonable first stab at a fix would be to make the default link colors match those used for question titles on the front page. Unfortunately, for some strange reason, those colors are set up exactly the opposite way from the usual convention: the unvisited links are dark and unsaturated, while the visited ones are bright and saturated. It works sort of OK on the main question list, but applying it to the whole site makes a lot of things (like the sidebar) look funny.
My eventual solution was to use the front page link colors, but flip them around to match the usual web convention (where visited links stand out less from body text).
After that, there were also some extra, redundant user profile page styles to override, and some related bugs to fix, not to mention that meta has its own, completely different link colors (which I ended up changing only slightly, to improve the contrast between the visited / unvisited default link colors). With all those things put together, here's the CSS ruleset I just added to the development branch (v1.27.7) of SOUP for math.SE:
/* invert front page link colors and make them the default: */
body a, body .question-hyperlink { color: #145d8a }
body a:visited, body .question-hyperlink:visited { color: #003b52 }
/* apply new colors on user profile page, too: */
body .user-show-new .question-hyperlink,
body .user-show-new .answer-hyperlink,
body .user-show-new .site-hyperlink {
color: #145d8a !important;
}
body .user-show-new .question-hyperlink:visited,
body .user-show-new .answer-hyperlink:visited,
body .user-show-new .site-hyperlink:visited {
color: #003b52 !important;
}
/* fix related bug with visited links in community bulletin: */
.module.community-bulletin a:visited { color: #32455d !important }
...and for meta:
body a { color: #a29131 }
body a:visited { color: #736722 }
.module.community-bulletin a:visited { color: #444 !important }
(The body at the beginning of each CSS selector is a kluge to make them just slightly more specific than the default math.SE style rules they should override.)
Here are some screenshots of the re-styled link colors:
Front page:

Search results:

User profile:

If you're used to the current front page colors, having them suddenly inverted may feel a little bit odd for a while. IMO, they start to feel natural pretty quickly, though.
If you'd like to beta-test this change before the next stable SOUP release, you can install the development version using a user script manager like Greasemonkey or Tampermonkey. Please note that the development release is updated frequently, and will, with probability approaching 1 as $t \to \infty$, occasionally contain bugs. If you spot one, please let me know!