Can't explain the first case, but the second case is almost certainly due to the Closed Captioning (CC) and related VBI program data (XDS?) support the Tivo has (theres a menu option under setup for this to enable on-screen captions, not sure about the rest).

The Tivo can insert (and obviously did insert) into the Video Stream going to your VCR (in the VBI signals between each "field" of the picture) details about the show such as title and other info, like captions.

Normally you need a VCR/TV that can read this stuff off the video signal as its played back - and it appears the VCR in this case could do this, and showed the "Show title" via the On-screen display as you observed.
[probably as it was CC enabled].

I don't know if the Tivo was showing the data coming from the local TV station signal, or if it was "making its own" up using the show info the Tivo has in its database of programs.

The Tivo can and does record the CC info on shows and can play it back both onscreen, and in the video stream you can record on your VCR.

This is also what the Tivo does with Macrovision - The Tivo will record any show (even one with Macrovision copy protection turned on), and will then "output" the Macrovision signals during playback to stop you recording the signal to tape if Macrovision was enabled during recording originally.
Thats why you can't record a DVD (with Macrovision enabled) to your Tivo, then copy it to tape to defeat Macrovision - of course if you were to extract the Video Stream from the Tivo then you could possibly defeat Macrovision that way.
But you all knew that anyway right?