Consider the following example in R:
library(TeachingDemos)
library(leaps)
fit1 <- regsubsets( Evap~MaxST+MinST+AvST+MaxAT+MinAT+AvAT+MaxH+MinH+AvH+Wind,
data=evap, nbest=5)
sfit1 <- summary(fit1)
(w <- which.max(sfit1$adjr2))
sfit1$which[w,]
fit2 <- regsubsets( Evap~MaxST+MinST+AvST+MaxAT+MinAT+AvAT+MaxH+MinH+AvH+Wind,
data=evap[-1,], nbest=5)
sfit2 <- summary(fit2)
(w2 <- which.max(sfit2$adjr2))
sfit2$which[w2,]
This does your strategy above in finding the model with the highest adjusted $R^2$, then it redoes the analysis leaving out the first data point. The 2 fits give different "Best" models (the differences are in whether to use Max air temp or Min air temp and whether to include Wind). You could redo this for leaving out each different point.
Would you really be comfortable calling a model the "Best" model knowing that a small change to the dataset (collected 1 less point) would have given a different "Best" model?