Found the problem:
I assumed that it was the Yoast WordPress SEO plugin causing my problem because if you disabled the plugin, my issue would go away.
As it turns out, it wasn’t the plugin’s fault at all. My site had been hacked. My .htaccess file had been altered and there were several malicious backdoor PHP files in the root folder for my website.
What was happening was that when I disabled and re-enabled the Yoast WordPress SEO plugin, the plugin was disrupting the redirect process that the hacker had setup on my site. That was why the problem disappeared when the plugin was disabled. After an undetermined period of time, the hacker would revisit my site and do his damage again. That is when my inner pages started getting the 404 errors.
The reason I was able to detect the hack was because I had disabled the Yoast plugin and left it disabled for more than one day. When I did that, the hacker then was able to take full control of the redirects and start sending my inner page traffic to his Russian spam/malware links. Once I saw my pages redirecting to spam – that is when the light bulb in my head lit up and told me it was a hack and not this plugin at all.
The way that the hacker got into my site was by exploiting a vulnerability in the TimThumb file that was being used by a different plugin on my site. I have since corrected the vulnerability and also removed the infection. Since then the Yoast WordPress SEO plugin has been operating as well as it always had prior to this incident.
My apologies go out to anyone who expended brain resources trying to figure out what was wrong with this plugin on my site. It was not the plugins fault at all. I am making a mental note for future reference to also check for malware/hacks the next time I suspect that a plugin is malfunctioning.
You would think that checking for malware or hacks would be common sense. Yet, my natural troubleshooting tendencies initially had me convinced it was this plugins fault. Ahhh…computers…
I hope my post helps someone else solve their issue. Beware of the .htaccess hack.
This site helped me identify the hack - http://sitecheck.sucuri.net/scanner/