I've seen this happen from time to time for at least the past year, so I don't think it's anything really new. I've been particularly aware of it because I moved a directory from one site (where the pages didn't really ever belong) to a subdomain on an appropriate site of mine that I moved to its own domain last August. Google had discovered some test pages on the original site, and a few on the old subdomain, which had been deleted a 2+ years ago. Only one or two of these pages had ever been linked to, even indirectly, but I still see the 404's from Googlebot's attempts to crawl them from time to time.
Both of these sites perform as I'd expect, so I don't worry about these stray 404's. And in general, I don't think even thousands of 404's would cause any problems if your sitemap doesn't include the URLs and there's no internal links to them. Search engines have to allow for an occasional restructuring on a large site without any negative implications.