The "integration" we refer to when we "integrate heavy fields out" is nothing else than the Feynman path integral – a way to calculate amplitudes in a quantum field theory using the sums-over-histories. If you have been thinking about any other kind of "integral" or if you even replaced the integral by contractions or arbitrary different operations, you had to end up with confusing (or completely wrong) conclusions.
The Feynman path integral gives you a formula for Green's functions and other amplitudes
$$ A = \int {\mathcal D}\phi_{\rm light} \,{\mathcal D}\phi_{\rm heavy}\,\exp(iS)\prod_{i}V_i$$
where $V_i$ are some insertions in the integral that are chosen according to the choice of the quantity (amplitude) we want to quantify. We integrate over all configurations of all fields etc. To integrate out $\phi_{\rm heavy}$ means to divide the integration process to two steps and first integrate over some degrees of freedom, namely $\phi_{\rm heavy}$ – which may be many fields – for fixed values of the remaining fields, $\phi_{\rm light}$.
The resulting i.e. remaining integral which still waits to be integrated over the remaining light fields (without insertions) is interpreted as $\exp(iS_{\rm effective})$ where $S_{\rm effective}$ only depends on the light degrees of freedom $\phi_{\rm light}$.
$$ A_\text{after integrating out} = \int {\mathcal D}\phi_{\rm light} \,\exp(iS_{\rm effective})\prod_{i}V_i,\\
\exp(iS_{\rm effective} [\phi_{\rm light}]) = \int {\mathcal D}\phi_{\rm heavy}\,\exp(iS)
$$
In this way, we eliminate the heavy degrees of freedom and calculate the effective action that remembers all the loop effects that the now-forgotten heavy fields used to cause. However, this effective field theory with an effective action – a result of integrating out the heavy fields – is only good for asking low-energy questions, of course. The insertions $V_i$ we may insert into the simplified theory that only depends on $\phi_{\rm light}$ cannot depend on the heavy degrees of freedom anymore, of course: they have been disappeared.
But in principle, if you calculate the path integral over the heavy degrees of freedom "exactly", the effective action may give you completely accurate results for the scattering of the light fields, and so on. In practice, we integrate over the heavy degrees of freedom "approximately" – we assume that the effective action only contains some low-dimension operators (the renormalizable ones and perhaps one or two extra operators that are non-renormalizable) and we study what happens with their coefficient. If we wanted the effective action to give exactly the same result for observables depending on the remaining light fields as the original action, we would have to include everything and the effective action would contain arbitrarily high-dimension non-renormalizable operators – equivalently, it would be non-local.
If you need to avoid the Feynman path integral, then you should interpret "integrating out a set of fields" by "finding the dynamics for the remaining fields that produces the same interactions or Green's functions for them as in the original theory that did contain the now-integrated-out fields". Feynman's approach gives us a straightforward tool to do such a thing; it could be very hard to derive the right algorithm in a different computational approach to quantum field theory.
