Examples for Decomposition Theorem
I can think of several additions to your list which don't seem to be represented yet.
1. Semismall resolutions
This first example is rather general, but afterward I will discuss how it is used in Springer theory.
First, suppose that $f:X \to Y$ is a proper map of stratified irreducible complex algebraic varieties with $X$ rationally smooth such that, if $Y = \cup Y_n$ is the stratification of $Y,$ the restriction of $f$ to $f^{-1}(Y_n) \to Y_n$ is topologically locally trivial (there's a theorem (not sure who it's by) that says we can always find a stratification such that this condition holds). Furthermore, we say that $f$ is semi-small if for each stratum $Y_n,$the dimension of the fiber of $f^{-1}(Y_n) \to Y_n$ is less than or equal to the half of codimension of $Y_n$ inside $Y.$ This condition is important largely because of the following theorem:
Fact. The pushforward of the constant perverse sheaf under a semismall map is still perverse.
Furthermore, we say that a stratum $Y_n$ is relevant whenever equality holds above, i.e., twice the fiber dimension is equal to the codimension. These will be important soon, as they will be the subvarieties appearing in the decomposition theorem.
By the assumptions we made on $f:X \to Y,$ we have a monodromy action of $\pi_1(Y_n)$ on the top dimensional cohomology group of the fiber of $f^{-1}(Y_n) \to Y_n.$ This corresponds to a local system $L_{Y_n},$ which we can decompose into irreducible components: $L_{Y_n} = \oplus L_{\rho}^{d_{\rho}}$ where $\rho$ runs over the set of irreducible representations of $\pi_1(Y_n)$ and $d_{\rho}$ are non-negative integers. We then say that a pair $(Y_n, \rho)$ is relevant iff $Y_n$ is a relevant stratum and $d_{\rho} \neq 0$ (i.e., $\rho$ appears in the decomposition of the representation of $\pi_1(Y_n)$).
Now we can finally state a theorem, which I believe is due to Borho and Macpherson, but perhaps others deserve credit as well. Keep the initial assumptions on $f:X \to Y,$ but now assume in addition that $X$ is smooth. Then a little work plus the decomposition theorem establish the following.
Theorem. $f_{\ast}IC_X = \oplus IC_{Z_n}(L_{\rho})^{d_{\rho}}$ where $Z_n$ is the closure of $Y_n$ and the sum ranges over all relevant pairs $(Y_n, \rho).$
This theorem is used in Springer theory (and perhaps other places as well). In this case, we want $f:X \to Y$ to be the Springer resolution. That is, $Y = \mathcal{N},$ the nilpotent cone of a Lie algebra $g$ associated to a reductive group $G$, and $Y = \widetilde{\mathcal{N}},$ the variety of pairs $(x,b)$ where $x \in \mathcal{N},$ $b$ is a Borel subalgebra, and $x \in b.$ If we stratify $\mathcal{N}$ using the $Ad(G)$-orbits (of which there are finitely many), then it turns out that the Springer resolution is semismall and every stratum is relevant.
It can furthermore be shown that the $L_{\rho}$ appearing in the theorem above correspond to the irreducible components of the regular representation of the Weyl group of $G.$ This can be seen as follows. There's an analog of the Springer resolution $\pi:\widetilde{g} \to g$ defined as above but with g in place of $\mathcal{N}.$ By proper base change, the pushforward of the constant sheaf on $\widetilde{\mathcal{N}}$ coincides with the pull-back (under the inclusion $\mathcal{N} \to g$) of the pushforward of the constant sheaf on $\widetilde{g}.$ Finally, since $\pi$ is what's known as a small map, the pushforward of the constant sheaf on $\widetilde{g}$ is equal to $IC_g(L)$ where $L$ is the local system on the dense open subset $g^{rs}$ of regular semisimple elements obtained from the $W$-torsor $\widetilde{g^{rs}} \to g^{rs}.$ From all this we obtain that the top-dimensional cohomology groups of Springer fibers produce all irreducible representations of $W.$
2. Geometric Satake
In a different direction, let me mention how the decomposition theorem is used in the geometric Satake correspondence (see the Mirkovic-Vilonen paper or the Ginzburg paper on this topic).
Geometric Satake is concerned with proving a tensor equivalence between the category of spherical perverse sheaves on the affine Grassmannian (i.e., perverse sheaves which are direct sums of IC sheaves) associated to a reductive group $G$ and the category of representations of the Langlands dual of $G.$ This is done through the Tannakian formalism, which in particular requires a tensor structure on spherical perverse sheaves. This tensor structure comes from a convolution product on perverse sheaves, meaning that it comes from a pull-back followed by a tensor product followed by a pushforward. In order to ensure that this operation takes spherical perverse sheaves to spherical perverse sheaves, we need the decomposition theorem.
Edit: According to the comments below, the decomposition theorem isn't actually needed to define the convolution product.
Comment on Kazhdan-Lusztig
I'm going to assume that Gil Kalai is referring to the work of Lusztig on Kazhdan-Lusztig polynomials and the Kazhdan-Lusztig conjecture (mentioned in his answer). In particular, they have a paper,
- [KL] Schubert varieties and Poincaré duality, D. Kazhdan, G. Lusztig, Proc. Symp. Pure Math, 1980
in which the coefficients of the Kazhdan-Lusztig polynomials are related to the dimensions of the intersection cohomology of Schubert varieties (which are not generally smooth, hence the appearance of intersection cohomology). At this point, the Decomposition Theorem had not been proved and was not used in [KL]. However, the proof of the Decomposition Theorem heavily uses Deligne's Purity Theorem, which also had not been proved at the time of [KL]. Kazhdan and Lusztig ended up giving a proof of the Purity Theorem in the special case they were considering (i.e., a proof for Schubert varieties). Given this, it's not too surprising that a few years later Macpherson and Gelfand gave a proof of the aforementioned result of [KL] using the decomposition theorem and the result explained at the beginning of this answer.
It's my understanding that Lusztig has another paper from the mid-eighties on finite Chevalley groups which uses the Kazhdan-Lusztig conjecture (proved in 1981) and the full machinery of perverse sheaves and the Decomposition Theorem (I've never looked at it though). Additionally, Lusztig's work in the late seventies and early eighties on Springer theory certainly hints at the Decomposition Theory methods eventually used by Borho and Macpherson (some of his conjectures are proved by Borho and Macpherson, for example).
A wonderful history and reference guide to much of this can be found in this article by Steve Kleiman.
One important class of examples is toric varieties where it gives a nice formula for the intersection homology.
(Shubert veraieties and the Kazhdan Luzstig polynomials is another example but I am not sure the decomposition theorem is needed, (the connection with IH was earlier). I think there are many further results in representation theory where the theorem is used a lot.)
This is not quite in the spirit of the question, but it seems worth pointing out that a lot of what you state when you ask the question is pretty imprecise: if X is a variety, and U is an open dense smooth subset, then for any local system L on U there is an intersection cohomology complex on X associated to L. If you take L to be the constant local system you get the "IC complex" you mention in the question. What the decomposition theorem says is that if f:X -> Y is a projective morphism, and X is smooth, then the derived push-forward Rf_*(Q) of the constant sheaf Q is a direct sum of shifted intersection cohomology complexes on subvarieties of Y attached to simple local systems. Also, the derived push-forward of the constant sheaf on a resolution of singularities doesn't in general have Q as a direct summand in any sense I can think of, so that example is not a good one. Maybe a better one is that if the resolution is small then the push-forward of the constant sheaf is the intersection cohomology sheaf (associated to the constant local system).
All this is better said using perverse sheaves, and you should think of it as a generalization of Hodge theory. There's a nice survey article in the Bulletin of the AMS by de Cataldo and Migliorini:
http://www.ams.org/bull/2009-46-04/S0273-0979-09-01260-9/S0273-0979-09-01260-9.pdf
this gives much more information and examples.