Warning: this used to be a great example, but I'm afraid it no longer is.
Let $H(n)$ be the number of horizontally-convex polyonimoes in the plane, where "horizontally convex" means just what you think it means, and equivalence is just up to translations (so mirror images and rotations are considered distinct). Using a sequence of manipulations with two-variable generating functions and an amazing amount of cancellation, one finds that
$H(n) = 5H(n-1) - 7H(n-2) + 4H(n-3)$.
I learned this from Gil Kalai in 1991 (and the result is much older), and I'm quite sure there was no known combinatorial proof of this surprising result for a while. However fairly recently Dean Hickerson found one. I'm sure Dean thought that this looks frustratingly like something that ought to have a combinatorial proof, and then he proceeded to resolve this frustration in the only possible way.