Residuals in regression should not be correlated with another variable This minitab post on checking residuals says:

If you can predict the residuals with another variable, that variable 
  should be included in the model.

I would think if we can predict residuals with another variable, then I  would not include that variable in the model. It is not clear to me why including the variable makes sense.
 A: This is based on the approach that there exists a set of explanatory variables (EV) whose variability captures everything in the variability of the dependent variable bar "random, unpredictable noise". As the link itself says clearly,

"The idea is that the deterministic portion of your model is so good at explaining (or predicting) the response that only the inherent
  randomness of any real-world phenomenon remains leftover for the error
  portion."

So, if the residuals $\hat {\mathbf u}$ from the regression of say, DV $y$ on EVs $\{X_1, X_2\}$ are correlated with some third variable $Z$ (which was not included in the regression), it means that the residuals do not behave like "random, unpredictable noise". So the set of EVs that was used, is not that set which "captures everything in the variability of $y$", and so it can be "improved upon". 
Let's see what this means in the merciless language of mathematics.  
We have the model (matrix notation) (and a sample of size $n$)
$$\mathbf y = \mathbf X\beta + \mathbf u$$ 
and let's assume that the nice properties for the OLS estimator to triumph, do hold:
$$Ε(\mathbf u \mid \mathbf X) = 0, {\rm Var}(\mathbf u \mid \mathbf X) = \sigma^2 I$$
Note that "the error is random, unpredictable noise" is not part of these assumptions. What the above says is that the error is unpredictable with respect to the specific set of regressors (check out the "Conditional Expectation Function" approach to linear regression).
Running the estimation we obtain the OLS estimator
$$\hat \beta = (\mathbf X'\mathbf X)^{-1}\mathbf X'\mathbf y = \beta + (\mathbf X'\mathbf X)^{-1}\mathbf X'\mathbf u$$
and from it the residuals. The residuals are an estimator of the error, and, since
$$u_i = y_i - \mathbf x'_i\beta =  \mathbf x'_i \hat \beta +\hat u_i - \mathbf x'_i\beta$$
we can re-arrange to get
$$\hat u_i = u_i - \mathbf x'_i(\hat \beta - \beta),\;\; i=1,...,n$$ 
So (and since moreover the residuals by construction have zero mean), being correlated with some variable $Z$, which is not in $\mathbf X$, it means,
$${\rm Cov}(\hat u_i, z_i) = E\Big(z_i\cdot [u_i - \mathbf x'_i(\hat \beta - \beta)]\Big) = E(u_iz_i) - E\Big(z_i\cdot\mathbf x'_i(\mathbf X'\mathbf X)^{-1}\mathbf X'\mathbf u\Big) \neq 0$$
Now, apply the Law of Iterated Expectations on the second term of the last expression to get
$$E(u_iz_i) - E\Big[E\Big(z\cdot\mathbf x'_i(\mathbf X'\mathbf X)^{-1}\mathbf X'\mathbf u\mid Z, \mathbf X\Big)\Big] \neq 0$$
$$\implies E(u_iz_i) - E\Big[z\cdot\mathbf x'_i(\mathbf X'\mathbf X)^{-1}\mathbf X'E\Big(\mathbf u\mid Z, \mathbf X\Big)\Big] \neq 0$$
The possible scenarios here are:  
A) $E(u_iz_i) = 0, \;\;\; E\Big(\mathbf u\mid Z, \mathbf X\Big) \neq 0$ 
In this case, if you follow the advice given, and re-run the regression of $\mathbf y$ using $\{Z, \mathbf X\}$ as regressors this time, you should know that, in the attempt to make the residuals behave as "random noise" with respect to other variables, not in $\mathbf X$  (which is far more ambitious than what we usually assume for our models), you will lose the finite-sample unbiasedness property of the estimator (due to $E\Big(\mathbf u\mid Z, \mathbf X)\Big) \neq 0$), but at least you will retain asymptotic consistency (due to $E(u_iz_i) = 0$, and under the assumptions already made). That's a good trade-off, Econometrics has long abandoned the hopes for finite-sample unbiasedness (and if you look around this site, you will find out that Statisticians in general have adopted, or pioneered, the same stance).
B) $E(u_iz_i) \neq 0, \;\;\; E\Big(\mathbf u\mid Z, \mathbf X\Big) \neq 0$
Here, you will lose both unbiasedness and consistency, and your estimator starts looking rather weak in good properties, to put it mildly, and I am not sure that "making the residuals random" justifies the price to pay. To my eyes, it doesn't because the estimates for $\beta$ are now very unreliable, and so the "random" residuals achievement becomes an artificial construct, and not a step closer to the true associations. And what if there is yet another variable $W$ which still can predict the new residuals obtained?
So the advice given may send you to better places, may send you to much worse places. Therefore, the critical issue is : Can you obtain evidence related to which of the two scenarios holds in a given case? - but this exceeds the scope of this answer.
The lesson I take out from all these is: "intuitive discussions" about "random and deterministic parts of a dependent variable", may be useful to a degree -but somewhere along the road, one should remember that the estimators that will be the ones that will eventually make concrete and tangible our attempts at estimation and inference, are mathematical tools with specific properties and specific limits to what they can do, achieve and guarantee. And some times they cannot achieve what appears "powerfully logical and intuitive" in a non-mathematical approach of the matter. 
A: Your residuals should be normal noise. If they have another structure you might have a problem like omitted-variable bias. You should then be able to predict the residuals by using the omitted variable(s). If you reestimate your model and now include the variable(s) you omitted before, then your residuals should be normal.
Or let me rephrase: You explain the dependent variable with the systematic part of the model (e.g. $X\beta$) and the (usually) unsystematic part, the residual. But, if the residuals have a structure apart from being random noise, then they aren't that "unsystematic", are they? Now if you can explain that structure with certain variables, then go on and include them in your model in the first place.
A: Another way to think about it is by analogy.  Box, Hunter & Hunter (in their "Statistics for Experimenters" which is highly recommended) uses the following analogy with chemistry and (drinking) water purification.  To purify the water, we pass it through some sort of filter to remove impurities. How do we test if there are left impurities? we take samples of the purified water, send it to a laboratory, and test for various chemical substances.
Now, in this analogy, the filter corresponds to our statistical model: The purpose of the model is to filter information from the data. To see if it worked, that is, it removed what there is of information from the data and left nothing, we test the residuals:  this is what is left after the filter took what it should.  Then we test the residuals to see if any impurities (that is, information) is left. An example of such is correlation between the residuals and some extra variable not used for the model. If that correlation exists, it means the residuals are not pure white noise (that is, clean water ...), and we try to extend the model (that is, the filter) to remove that information also. One way of doing that is including that extra variable in the model!
