Originally Posted by cyanide

This is what I would do. With a few hunderd pages it will take some time to add them all as 301's, but well worth it.

A 301 Re-direct is the "official" way to tell the SE's that your pages have permanently moved.

You probably had some issues before, because you moved to a new domain. In this case, your domain is still the same, so the change should get picked up quicker.