This occurred with my old site. It takes the search engines a few months to update and make the changes. It took approximately 2 months for Google to remove my old site URL's from its SERP and now only my current pages appear. Try submitting a new site map to all the search engines that you have this problem with. This will help fix the problem.

__________________
Increase your websites search engine optimization rankings with SEO Optimizers Consultant Services or read about the latest news and updates at our SEO and SEM Blog