How Recent Is the Divergence In Taiwan- and PRC-Accented Mandarin Speech?
Actually, until around the 1990s, the spoken language in official sources were very similar.

Famous singers like Teresa Teng spoke pretty much like people from China nowadays. Here's an example of an interviewee from those earlier days: https://www.youtube.com/watch?v=cWEcZvhfnzA&amp;hd=1 (There's a great quote about how Teresa Teng's songs brought comfort for those miserable mainlanders!). There's a lot more stuff from those earlier days you can search via youtube.

There are a couple of important factors as to why they diverged.
1) The northern parts of Taiwan are its political/economic center and early on home to most of the refugees from Mainland China. Because of this, they strongly emphasized standard Mandarin as a sign of status/power etc. However, on the other hand, southern Taiwan has always been home to Chinese variants different from the mainland due to the influence of the people who were there before the KMT came to power.

2) Until the 1990s, the KMT strongly enforced a 国语运动 (presumably the 国语 back then was similar to how mainland Chinese is now). This meant if you were at school, in public, in meeting involving more than 3 people and you were found to be using a (gasp) non-国语 language, you would be heavily punished (3000-10000 元).  (Here's wikipedia on this: http://zh.wikipedia.org/zh-cn/%E5%9C%8B%E8%AA%9E%E9%81%8B%E5%8B%95)

3) In the 1990s the DPP started to gain traction in south. They advocated a Taiwanization movement. They wanted to have a Taiwan distinct from China. This meant no more 国语运动 and allowing for more of the Chinese variants.

In summary, I would say that Taiwanese variant of Chinese has always had some amount of difference from the mainland. However, because of various political reasons, those variants were never heard publicly. In some aspects, they were suppressed. But with the rise of a more tolerant government and the Taiwanization movement, Taiwan wanted to carve out a distinct variant of 国语, and thus we now have quite a big difference between the mainland and Taiwan.