You can also get a recursive formula without residues:
Let $I_s(a)=\int \frac{\cos(ux)}{(x^2 + a^2)^s} \ \mathrm{d}x$. Then
$ \begin{eqnarray} \frac{\mathrm{d}I_s(a)}{\mathrm{d}a} &=& \frac{d}{da}\int_{-\infty}^\infty \frac{\cos(ux)}{(x^2 + a^2)^s} \ \mathrm{d}x \\ &=& -2as \int_{-\infty}^\infty \frac{\cos(ux)}{(x^2 + a^2)^{s+1}} \ \mathrm{d}x \\ &=& -2as I_{s+1}(a) \end{eqnarray} $
This is the recursion. So with $I_1(a) = \pi e^{-au}/a$, we get for $s = 2$
$ \begin{eqnarray} I_2(a) &=& \frac{-1}{2as}\pi(-u/a - 1/a^2)e^{-au} \\ &=& \frac{\pi e^{-au}}{2a^3s} (au+1) \\ \end{eqnarray} $
and in general
$I_{s+1}(a) = \frac{\pi}{2^{s}s!}\left(\frac{-1}{a}\frac{\mathrm{d}}{\mathrm{d}a}\right)^{s} \ \frac{e^{-au}}a$
Observation: The operator $\left(\frac{-1}{a}\frac{\mathrm{d}}{\mathrm{d}a}\right)^{s}$ also turns up in the same sort of relation for the Bessel functions $J_n(x)$, where we have
$J_n(x) = \left(\frac{-1}{x}\frac{\mathrm{d}}{\mathrm{d}x}\right)^{n} J_0(x)$
for $n\ge 0$.
Additional Question: Is this a coincidence or can the integral somehow be nicely expressed in terms of Bessel functions? Is there a deeper relationship?
Also, the formula derived by Jonathan in the other post
$ \begin{eqnarray} I_s(a) &=& \frac{2\pi i}{(s-1)!} e^{-au} \sum_{k=0}^{s-1} {s-1 \choose k} (-1)^k (iu)^{s-1-k} \frac{s!}{(s-k)!} (2ia)^{-s-k} \\ &=&\frac{\pi u^{s-1} e^{-au}}{2^{s-1}a^{s}} \sum_{k=0}^{s-1} \frac{(-1)^k s! }{(s-k)\, k!\, {(s-1-k)!}^2}\frac{1}{(2au)^k} \end{eqnarray} $
does have some resemblence to the series expressions of Bessel functions.