If we're understanding the situation correctly, I'd say this sums it up pretty well.

So, I'm confused - are you looking to keep both sites active? If you're just moving the tools to a new domain, you could NOINDEX the old pages. If the link-based penalty isn't too severe, you might try a cross-domain rel=canonical on the old site. Unfortunately, without understanding the penalty profile, it's a bit tricky to advise. It's really a cost/benefit trade-off - how much risk of carrying the penalty are you willing to accept vs. the alternative of cutting off all authority and starting over on the new site.

If you've had Panda-related problems, though, I wouldn't keep the tools crawlable on both sites. That seems more likely to prolong your problems than it is to solve them.

I tend to agree with Martin - it seems like there's probably a way to preserve some of the power of the old site and 301-redirect selectively (or potentially use cross-domain rel=canonical tags), but it would take a much deeper understanding of the site than Q&A allows.

If you rebuild the site from scratch, you'd almost always want to de-index the old site. I'd flat out remove it via Google Webmaster Tools - it's the fastest method. Leaving both sites crawlable is only going to compound your problems and haunt the new site.

I'd warn, though, that if this is Panda-related, just moving the content won't solve your problems. You do have to sort out why they happened in the first place, or the same algorithmic issues will just come back. In other words, if the problems are content-related, then it doesn't really matter where the content lives. If the problems are link related, then moving will remove the problems. Of course, moving will also remove and advantages you currently have based on good links.

Unfortunately, this isn't a problem that can be addressed without a pretty deep audit. My gut feeling is that there may be a way to preserve some of the authority of the old site, but you really need to pin down the problems. Panda + Penguin is a wide swath of potential problems and just isn't enough information to do this right.

So, here's the problem - if you follow the official uses of our options, then there is no answer. You can't have thin content or Google will slap you with Panda (or, at the very least, devalue your rankings, you can't use rel=canonical on pages that aren't 100% duplicates, and you're not supposed to (according to Google) just NOINDEX content. The official advice is: "Let us sort it out, but if we don't sort it out, we'll smack you down."

I don't mean that to be critical of your comment, but I'm very frustrated with the official party line from Google. Practically speaking, I've found index control to be extremely effective even before Panda, and critical for big sites post-Panda. Sometimes, that means embracing imperfect solutions. The right tool for any situation can be complex (and it may be a combination of tools), but rel=canonical is powerful and often effective, in my experience.

You should be able to customize a 410 just like you do a 404. The problem is that most platforms don't do that, by default, so you get the old-school status code page. That should be configurable, though, on almost all modern platforms.

This can get tricky when you dive into the details, but I general agree with Takeshi and EGOL - consolidate or canonicalize. If the products are different brands/versions of a similar item, it's a bit trickier, but these variations do have a way of spinning out of control. In 2013, I think the down side of your index running wild is a lot higher than the up side of ranking for a couple more long-tail terms. It does depend a lot on your traffic, business model, etc., though. I'm not sure any of us can adequately advise you in the scope of a Q&A.

Let me add, though - if you're already 301ing a ton of expired listings at large scale (in the thousands), I'd try to ease this in gradually. Maybe just 404 new ones and then start switching the back-log. I'm always hesitant to switch signals on thousands of pages at once.

This is a point of disagreement among many SEOs, but at that volume AND if people rarely link back to the individual property pages, I would lean toward 404s over 301s. It's just going to be more Google-friendly at that scope. The other option would be to develop some kind of permalink structure that you could re-use as properties change, but that really depends a lot on the logic of your site and can get pretty complex.

It's really hard to advise without knowing more about the site, but consolidating the different types of rentals may be a good bet. If those search types are useful for visitors, then don't 301-redirect. I'd probably use rel=canonical here, or META NOIDNEX those variants.

Inactive listings are tougher. If they don't attract links and won't become active again in the future, then I think 404s are ok. A very large number of 301s that grows rapidly over time can start to cause problems and raise some red flags. It's fairly rare, but it has happened.

Removing the cities with no data is a good bet. You could META NOINDEX those, if they aren't typically linked to. I find that NOINDEX is easier to reverse later than canonical or 301. It's not an exact science, I'm afraid, and it often depends on the size of the site and the crawl architecture.

I try not to over-interpret toolbar PR, but 500K indexed URLs for a PR5 site is, on the surface, likely to create problems for you. Best-case, your ranking ability is diluted across way too many pages. Worst case, you could encounter something on the scale of Panda.

Either way, at that scale, clean-up really can help. It is not an easy process - it takes time, and even best practices usually have to be adjusted to match the site structure and Google's reactions to your changes. For a site that size, it's really hard to give you quick and easy answers to where to start, but if there are reasonable ways to consolidate large numbers of "thin" pages, then I'd definitely consider that.