The assertion that Random Forests does not perform well with large datasets is absurd. It is notably well suited to high dimensional problems both from a sample size and multivariate standpoint. The primary issues with RF and very large problems are: 1) tractability and 2) sample balance.
If you have a problem where one class is proportionally larger (>30%) then the bootstrap can be biased and the OOB validation, and possibly the estimate, is incorrect. The result, of say a binary problem with [0=10000,1=200], would be a very high prediction rate to 0 and very low to 1 resulting in a very good, but quite inflated, OOB error rate for the model but very poor performance for class 1.
This is obviously not representative of the model performance and you will have very low prediction prevalence for class 1. If you have a class balance issue I would follow the methodologies in either Chen et. al., (2004) or Evans & Cushman (2009).
Chen C, Liaw A, Breiman L (2004) Using random forest to learn imbalanced data. http://www.stat.berkeley.edu/tech-reports/666.pdf
Evans, J.S. and S.A. Cushman (2009) Gradient Modeling of Conifer Species Using Random Forests. Landscape Ecology 5:673-683.