Why does calcium carbonate decompose into calcium oxide?
Some quick googling did not turn up a definitive reaction mechanism, and most of the papers I did find seemed to instead be focused on the overall reaction rate and controlling factors - probably because this is such an industrially important reaction and (at least according to this article) gas transport is the rate-limiting factor - this is common for heterogeneous reactions.

However, it is not too hard to propose a plausible mechanism. I would suggest the same mechanism you did - what is likely happening is that the oxygen near one calcium ion can pull some electron density away from the carbon, leaving $\ce{CO2}$ which diffuses away as a gas. The calcium ion stabilizes the new oxygen anion and forms a new, different lattice structure.

As @Martin points out, the reason that this process is thermodynamically favorable is that the products have a higher entropy. The standard Gibbs free energy of reaction (using data from Tro's Chemistry) is:

$$
\begin{align}
\Delta G &amp;= \Delta H - T\Delta S \\
&amp;= 179.2\space kJ/mol - T(0.1602\space J/mol*K)
\end{align}
$$
Note that $\Delta H$ is positive, but so is $\Delta S$.
At 298 K (room temp) $\Delta G = 131.3 \space kJ/mol$ - the reaction is not favorable.

The equilibrium temperature (ignoring temperature corrections) should be around 1120 K.