JFW 3.5 does a good job with tables. If a popular screen reader like JFW or Window-Eyes can handle tables fine, then I would say that those tables are accessible. Some of this responsibility must come from our end. We can't expect everyone to do more extra accessibility work than is really necessary. If screen readers exist which can handle a particular structure, than that structure is accessible, so long as it is implemented in a way that screen access software can read.
Many sites are accessible, but they are tedious to get around.
They are accessible. We must learn and use various techniques, and add even greater functionality to our screen readers, to make the browsing process even better. A reasonably modern screen access system can be assumed. Again, I believe it is the responsibility of the content provider to make the content accessible, not to make sure that the page works correctly with Lynx. Scripting and other modern web design tools and techniques just aren't supported in older browsers like Lynx, and we will be up a creek without a pattle if we expect content providers to roll back their modern web sites.