Based on your question I can think of four possible issues with statistics that could be causing the issues that you're experiencing.
1. Statistics are not automatically updated often enough.
In SQL Server 2012, statistics are updated only after 20% or more of the rows in the table have changed. That means that for a billion row table you will need to modify 200 M rows before a statistics update occurs. As the table grows larger your statistics updates will become more infrequent, so SQL Server can go for years without updating statistics on large tables.
TF 2371 changes the threshold so that statistics updates occur more often. In SQL Server 2016 this change has been made my default.
2. Queries in your workload are vulnerable to the ascending key problem.
Consider a table which has new data loaded daily and queries that filter on the latest day of data. Unless statistics update updated immediately after the data load the new data will not be present in any of the statistics histograms. That can result in very poor query performance due to low cardinality estimates.
The new CE in SQL Server 2014 makes improvements in this area. If you ask for data outside of the histogram range it may make a more optimistic guess and assume that there is data in the table but not in the histogram. In SQL Server 2012 you can address this problem, if you have it, by updating statistics more often or by enabling TF 4139. TF 4139 only works against columns with an index on them. SQL Server may run a very quick query against the index to get the highest or lowest value and will temporarily amend the histogram of the relevant statistics object. This can result in much better plans for some queries.
3. Your queries wait on statistics updates.
By default, if a query loads a stale statistics update it will update that statistics object before creating a query plan. On SQL Server 2012, sampled statistics update will run with MAXDOP 1. If kicked off against a large table the process may timeout while waiting for the statistics update to complete. After you update statistics against the tables the query performs better because it no longer has to wait for the statistics update.
If you're running into this problem this can be addressed by more proactive statistics maintenance with the NORECOMPUTE option. Alternatively, you can try to make the statistics update faster by Upgrading to SQL Server 2016. On SQL Server 2016 sampled statistics updates can run in parallel.
Another option is to turn on the AUTO_UPDATE_STATISTICS_ASYNC option. If a query plan encounters a stale statistics object it will queue that statistics object to be updated by a background job. This might sound bad and it is. The query may execute with stale statistics. This is the kind of feature that you want to turn on when you don't have a better choice, such as when working with large systems where auto statistics updates are too expensive or just don't help with plan shape enough. Jack Li blogged about a customer that was helped with this option here.
4. Your workload would benefit from manual statistics updates with a higher sample rate than the auto sample rate.
Some queries and workloads need more than the default sampled rate of statistics to achieve acceptable performance. This can be difficult to do on a large database but there are a few tricks and a few enhancements in later versions of SQL Server which will help.
If you know your data and workload very well you may be able to turn off automatic statistics updates. You can gather statistics that you need with FULLSCAN and update them when appropriate. This approach will require a lot of work and a lot of attention paid to the server.
If you have an existing maintenance process that rebuilds indexes (the wisdom of that is debated) note that rebuilding indexes automatically updates stats with FULLSCAN, so perhaps you can take advantage of that if you build a maintenance solution to update statistics.
Note that gathering sampled statistics may not be faster than fullscan statistics, especially if the histogram column is indexed. SQL Server can do fullscan statistics updates in parallel. It may also avoid a sort when doing a fullscan of an indexed column but will not avoid the sort when sampling the column. In fact, for large enough tables statistics updates against unindexed columns can fail if they fill up tempdb.
SQL Server 2014 introduced incremental statistics. Suppose that you have a partitioned table and lots of data is modified in just one partition. Previously, to update the statistics on the table you would have had to look at all of the partitions. With this new feature it is possible to just gather new statistics on the changed partition. SQL Server is able to roll up the statistics from the partitions into one table level object.
If you aren't able to upgrade you could consider converting some tables to partitioned views. Each table within the view will get its own statistics objects, so if you load data according to date you may only need to update statistics on the latest table in the view instead of all of the tables of the view.
Finally, as mentioned before, SQL Server 2016 can update sampled statistics in parallel:
Starting with SQL Server 2016, sampling of data to build statistics is done in parallel, when using compatibility level 130, to improve the performance of statistics collection. The query optimizer will use parallel sample statistics, whenever a table size exceeds a certain threshold.
