Verkehrsverbünde

Regional public transportation in Germany is run by some subsidiaries of German Rail

Thank goodness that is not the case, otherwise we would still be there today, where we were in 1980 ...;) A "Verkehrsverbund" is a combination of all relevant transport companies in a given area, mostly in the legal form of a limited company (GmbH). Of course the DB is mostly the largest carrier (not always: an exception is e.g. the Hamburger Verkehrsverbund HVV), and usually by far the least enjoyable from the viewpoint of all others. For example, the VGN, in terms of area the largest VV in Bavaria, has 31 participating companies.

A list of all VV's is here.

Most of Germany (and Switzerland) is covered by Verkehrsverbünde. The link sla019 gave has a map of them all. They often correspond to counties (Kreise) or groups of counties. The literal translation is "Transport associations", but a better description would be "combined ticketing areas".
The main feature is ticketing is not per journey and distance (as it is for trains outside Verkehrsverbünde), but by zones. The Verbund is divided into zones. Tickets are based on the number of zones you travel in or through. Within a zone, you can change and use any method of transport (train, bus, U-Bahn , tram) on the same ticket.
For example Small-town is one zone, City-centre is another, with one zone in between, so that is a 3 zone ticket. But, you can get on a local bus on the edge of Small-town, and buy a 3 zone ticket from the driver, and that will allow you take that bus to Small-town station, DB train to City-centre and city-owned U-Bahn to your final destination, all on the same ticket.

This of course means DB fares don't apply, DB gets a cut of the 3-zone ticket. But it would be nice if that "Fares not available" message included a link to the Verkehrsverbund website.

It is not perfect but I can usually find the applicable Verkehrsverbund by googling it. Example- googling Verkehrsverbund Rothenburg will give you the VGN or Verkehrsverbund Großraum Nürnberg. That might work for me as I usually stick to trains and moderate sized cities.

DB’s website is getting a little more helpful. Taking the train from Würzburg to Bad Mergentheim, I noticed it gave VRN fare.

SLA: Nice website, but it would be nicer if the links were to the actual VV website, not Wikipedia articles. Some of the linked-to articles link to the actual website (find the link under EXTERNAL LINKS). If not, you can usually find the website by Googling the full name of the VV, ex. "Verkehrsverbund Mainfranken". Also, a lot of VVs managed to get www. VV name .de. For instance VGN, Verkehrsverbund Großraum Nürnberg got www. VGN .de, or RMV.de for Rhein-Main Verkehrsverbund (Frankfurt), but in other cases, some business got there first, so often they will use info, like vrm-info.de or vrm.info for Verkehrsverbund Rhein-Mosel.

Taking the train from Würzburg to Bad Mergentheim, I noticed it gave VRN fare.

It doesn't give the actual fare, it just says "VRN fare". At least it tells you where to look.

Verkehrsverbünde often govern fares into neighboring VVs. Bad Mergentheim is in VRN but Würzburg is in VVM. Although VRN's website gives a fare from Bad Mergentheim to Würzburg, VVM doesn't give a fare from Würzburg to Bad Mergentheim. On the other hand, the Bahn doesn't give the RMV fare from FRA (in RMV) to Bacharach (in RNN).

Gary
"Taking the train from Würzburg to Bad Mergentheim, I noticed it gave VRN fare."

Lee
"It doesn't give the actual fare, it just says "VRN fare". At least it tells you where to look."

Sure it gives you the fare. Just click on offer selection.