Cross-domain canonical is the most viable option here. As Mike and Chris said, it is possible for Google to ignore the tag in some cases, but it's a fairly strong suggestion. There are two main reasons I'd recommend it:

(1) Syndicated content is the entire reason Google allowed the use of rel=canonical across domains. SEOs I know at large publishers have used it very effectively. While your situation may not be entirely the same, it sounds similar to a syndicated content scenario.

(2) It's really your only viable option. While a 301-redirect is almost always honored by Google, as Chris suggested, it's also very different. A 301 will take the visitors on the partner site page directly to your page, and that's not your intent. Rel=canonical will leave visitors on the partner page, but tell search engines to credit that page to the source. Google experimented with a content syndication tag, but that tag's been deprecated, so in most cases rel=canonical is the best choice we have left.

Wow, that's a tricky one. I haven't seen a lot of good data on rel="alternate" hreflang="x" yet, other than general suggestions that it's worth trying and seems to sometimes work. Technically, Google would say that the green/red/yellow versions aren't true duplicates, but practically, I think the canonical here is a good approach.

My gut feeling is that the canonical will overpower the hreflang - adding the alternate language versions to the color variants won't hurt you, but it probably won't do anything. If it were me, I think I'd go with your first approach - just add the hreflang tag to the canonical version and leave it off the variants. Monitor that - see how it impacts your international rankings, and go from there.

Alan's absolutely right about how canonical works, but I just want to clarify something - what about these pages is duplicated? In other words, are these regular searches (like product searches) with duplicate URLs, are these paginated searches (with page 2, 3, etc. that appear thin), or are these user-generated searches spinning out into new search pages (not exact duplicates but overlapping)? The solutions can vary a bit with the problem, and internal search is tricky.

I'd tend to agree. It won't harm you to go over, but since no one's going to see it, what's the point, generally. Now, if you feel thinks are being cut off arbitrarily (like the name of a product) and those keywords should be included somehow, fine - go over the limit. You can potentially rank for those terms and they may show up in other places. Some directories, social networks, etc. read the title tags, too.

If it's just ego, though, like a long brand name, I'd suggest letting it go. Unless you're a really big brand, it's not going to matter that much, and you're likely to rank for your brand anyway. If the brand is getting cut off, then name recognition won't help your CTR anyway.

Usability research definitely shows that people pay much more attention to the front of a headline, and even just the first two words, so even if a longer title "makes sense", people may not care or even see it. So, sometimes, I think we obsess over getting something just right that may not end up mattering that much, practically.

Personally, I'd pick a different battle with the client, and maybe just keep a few long that are critically important.

Yeah, normally I'd say to NOINDEX those user-generated search URLs, but since they're collecting traffic, I'd have to side with Alan - a canonical may be your best bet here. Technically, they aren't "true" duplicates, but you don't want the 1K pages in the index, you don't want to lose the traffic (which NOINDEX would do), and you don't want to kill those pages for users (which a 301 would do).

Only thing I'd add is that, if some of these pages are generating most of the traffic (e.g. 10 pages = 90% of the traffic for these internal searches), you might want to make those permanent pages, like categories in your site architecture, and then 301 the custom URLs to those permanent pages.

I think that situation's a bit different - if you aren't interlinking and the sites are very different (your site vs. customer sites), there's no harm in shared hosting. If you share the IP and one site is hit with a severe penalty, there's a small chance of bleedover, but we don't even see that much these days. Now that we're running out of IPv4 addresses, shared IPs are a lot more common (by necessity).