That is not why you're not supposed to use tables for layout. It is for accessibility reasons. This is routinely ignored because approximately 0% of rich web apps are accessibility-friendly and people with screen readers have pretty much just learned to make do.

This is such an oversimplification. Since when did a table contribute to the richness of an application? Most modern sites are built with divs and remain inaccessible.

Tables simplify the code for simple content placement. That's it. It's only one of a long list of requirements to satisfy all sorts of requirements including screen reader compatibility. And if one were to use tables, it's only one of a long list of hacks and non-hacks that would break screen readers.

The root of the problem is with web designers not prioritizing accessibility-friendliness in their sites to begin with, for the basic reason that it prevents them from building the site that they need to build. And "what breaks or doesn't break accessibility" is not part of the spec description and is not enforced technically. We get recommendations, but it's up to us to test everything against everything else and compromise. Not just with accessibility but with everything else as well including backwards compatibility.

Wouldn't accessibility software back then have been able to deal with table based layout, considering most websites were constructed that way?

No, they weren't, at least not usefully. It was a major problem and made a lot of the internet unusable for vision-impaired people.