Responding to your 3rd paragraph. I think you are too pessimistic. Solving the general case probably is that hard. But working "well enough", "most of the time" probably isn't. I'd think a clever selection of hacks, combined with a knowledge of the most common patterns in which websites are designed go a very long way.

Afaik googlebot does things like this already. It detects hidden elements to prevent blackhat seo for instance.