I know this is off topic to what you were expecting for an answer but, well, you may want to reconsider changing your statistics job to skip the nightly FULLSCAN and opt for something a little lighter (like just COLUMNS), perhaps leaving FULLSCAN for a weekly deal (just a thought) - it might help out with what I suspect is a long running process and a whole lot of consumed resources? Although you didn't mention it, I assume you have an index maintenance rebuild/reorg in place as well?

Regarding the current size and anticipated growth - It's really not that bad, we have nearly a billion rows in some tables, with the majority of our larger tables in the 300-500 million range. Thoughtful indexing and query optimizations can REALLY GO A LONG way in keep things running smoothly. Since you mention that you have little control over how the queries are built, you may want to further evaluate these queries to look for patterns with WHERE clauses, JOINS, etc, and possibly look into filtered indexes (since this isn't an enterprise-level feature). Obviously there are pros/cons to that as well but it just may help for those "BIG" queries involving the JOINS to the larger tables.

For the queries generating "sub-optimal" plans, dive deeper into the execution plans to see why you're getting scans rather than seeks, surely there is something you can do to optimize those (of course not everything is possible in certain cases). We have a similar situation (auto-generated queries by an external 3rd party vendor app), but we isolate the problematic queries and "recommend" (make) the vendor incorporate our changes so they perform better when critically necessary.

I honestly don't know where the "tipping" point is for extremely large data sets and where possibly a scan takes the same amount of time as a seek would (if there is even one), but I can tell you it's not where you are now....perhaps others on this forum with more experience in this area can help shed some light to this topic?