All designs involve compromises
A design is a compromise between various tradeoffs - that is a key concept to comprehend. The topic of your question is an example of such tradeoff - underlines make links easy to find by mere visual inspection, but they add visual noise and are considered by many counter-aesthetic. Colours, not only reduce accessibility, but they add visual noise of their own and reduce the designer ability to guide the user eye to where it really needs to go.
The role of the designer is to control such tradeoffs so the final design best serves the majority of the target audience.
There are many variables and considerations that inform design decisions, and these truly change on a case by case basis. For instance, one important consideration is the ratio between first-time visits and repeated visits. Sites that serve largely repeated visitors can get away with reduced usability for first time visitors, yielding a cleaner interface for repeating visitors. This is particularly the case if the learning involved is low, like having to hover over something to see if it is clickable.
Guidelines are just that
If you agree that all designs are compromises and that design decision should account for many variables that are largely unique to each system, then you should understand why any set of design rules may cause more harm than good.
Guidelines are not rules, but they are a set of instructions made to be adhered to. But they may be as bad for designs as rules. Regardless what guideline you come across, there is always a chance it won't be appropriate in a particular context.
To give one example, one of Nielsen's Heuristics is:
Aesthetic and minimalist design
This will go against the brand image of many companies, who may wish to project, for instance, a message of budget brand.
We are smarter than (some) designers think we are
It has been many decades since psychologists have demonstrated the brain's outstanding ability to successfully interpret and make sense of things when the information provided is extremely limited and even confusing. For instance, most people are marvelled when they learn for the first time they can read the following:

Who would have thought!
For the cognitive scientist this is all too obvious - the brain is a highly capable associative machine where context can radically shape interpretation (just think how many different meanings the word 'or' has, yet we hardly ever struggle to get the correct one without even trying). You wouldn't normally see 17 as 'it', but you just did, and rightly so.
You would, in fact, be surprised how you may fail to spot a colour-blind person even after years of frequent engagements. You may even fail to spot one during user testing! Yes, underlines do help them, but the lack-of only slows them down and they learn to compensate for the lack of colour by other cognitive means so the damage of colour-reliance is often less than what designers think it is.
So many psychologists know that even the faintest clue, or the faintest pattern, can lead to successful interpretation.
I think that the UX field is slowly acknowledging that we may have discredited the cognitive abilities of users for too long. You see more and more designs based on comprehensive cognitive analysis rather than general guidelines, which in turn gives designers a higher ability to craft effective visual designs.
Mostly this is done by reliance on implicit clues and cognitive deduction rather than providing explicit features. What is important to assert is that it is clear to everyone that interpretation time rises when no explicit features are involved, which applies a great deal to new users, but even to frequent users. However, with repeated use, the ability to clean-up the interface from unwanted noise and to guide the user eyes to the relevant places can mean that the overall interpretation time while completing a complex task is reduced, but only after users have became accustomed to the interface.
To give one great example of this, here's the interface of an Alarm Clock mobile app called Rise:

The interface does not make it obvious in any way how do you turn the alarm on or off. Users are left with a few options:
- Either try different gestures.
- Search for a help option through the settings icon (at the bottom) - also highly implicit.
- Refer to the developer's site.
In my case, I went for the former to discover that a swipe to the right toggles the alarm. So first usage took time and the design was nothing short of cryptic at that point. But henceforth, you set your alarm much quicker than on other apps, and there's no visual searching or interpretation to be done - you don't even have to search for an on switch, even if such would exist on the screen!
Underlines should be least of your worries on StackExchange
If you look at this page, you'll find a multitude of elements that are interactive with nothing to suggest so:
- All global navigation elements.
- The primary nav elements.
- The share, edit, flag links.
You can argue that it is implicit or deductive that these are clickable, but in the case of the share, edit, flag links there's a stronger argument - in its wish to complete a task, a user articulating in their mind "I wish to edit this post" will cause the brain to see the word 'edit' better than others (in the same way telling someone 'strawberry' will momentary increase their visual ability to identify all red things). So if it's an action link, and is phrased as a verb, you can pretty much be certain that most users will predict that it is interactive even before hovering.
Anyhow, it only takes a few usage iterations to get it, and ask yourself if you have ever struggled with or even was slowed down by the fact that there is nothing to signify the interactive nature of the elements in the bullet list above.
Summary
I have not provided a definite answer for when underlines should be used, but I have argued that no such definite answer exists for the following reasons:
- The problem each design solves and the target audience vary greatly between projects.
- Guidelines are great but an informed judgement has to be made as for when to adhere to them.
- Design is about finding the appropriate balance between various tradeoffs.
- Designers should account more to cognitive abilities and the cumulative efficiency of a design rather than a localised one.
And so to answer the question in your title:
- Because the site is heavily based on repeated usage rather than single visits, the designers chose to reduce usability for newcomers so to increase usability for frequent visitors (the bulk of users). This is even more so the case with colour-blind people.
- The site is not heavily commerce oriented, and it has next to no competition. Again, this means the business doesn't have to prioritise first-time-users as much.
- The designers are likely to have assumed that visitors will have high-motivation to use the site; this gives them a bit more leeway making things less obvious at the onset.
- Because the site designers are familiar with and supportive to what seems a current UX trend - to relay more on cognitive analysis.
Most of these points apply to Google as well, but just because they don't use underlines doesn't mean any design shouldn't.
My gut feeling is that had the StackExchange (or Google) designers had to design an e-commerce site for the elderly, they would have probably go for underlined links.