I've been battling Google Analtyics for the last week for two customers with a similar issue - each has a multi-step goal configured starting on one domain and ending on another.
As I understood it you add the tracking code to your store site and your third party shopping cart pages. What I didn't realize and have never witnessed before, is that you must add the code to every page in your store and every page in your third party cart. I found this out when I found a different Google Support page on the topic than the one I had read earlier.
The first symptom that something was wrong was a funnel with a required step only reporting the first page despite a simple series of steps defined. I just couldn't understand why the second page which was part of the same domain was no longer tracking since I added the cross-domain linker updates.
Next I re-read the page I referenced first above and realized that the cross-domain script goes on the destination as well as the source page but it didn't fix the funnel. However, I was able to use the GA Navigation Summary (Content > Top Content > Page detail > Navigation Summary) to find each page of the flow. Everything was being tracked here but not in my funnel. Hmm. If you are on the Navigation Summary you should see step 2 of your funnel as the exit to step 1 but that wasn't the case.
I searched for step 2 in the content dropdown and found it so I clicked that to see the Navigation summary for step 2. Here I saw entrances but no step 1 as previous pages. Stranger still, I could see step 3 (on the shopping cart domain) as a next page! For step 3 as the navigation summary though - I couldn't see step 4 so I was missing 1 & 4.
It was clear GA wasn't tracking the progression from step 1 > step 2 and starting a visit with step 2 somehow, recording step 3 next then ignoring the progression to step 4.
The light bulb moment came when I guessed correctly that the use of the linker script on step 2 and 3 meant step 1 was tracked with one cookie before step 2 announced the need to mark pages as part of the domain "none" so it created a second cookie.
The step 3 page also uses the "none" domain and so continues with the second cookie since the linker has passed enough info along to set a matching cookie on the new domain.
Step 4 (thank you on shopping cart) didn't have the linker script so GA created a third cookie because the shopping cart domain didn't match the "none" domain set by the linker on step 3.
I ran a test and, sure enough, my funnel started working again. Pah.
The bottom line is that when I re-read the wording on the reference pages, I'd missed the subtle fact that you don't just tag the pages involved in the link but every page in your domain that are to be tracked when you do anything with third party domains to make sure your Google Analytics setuprecords every click.

Here's a tricky question:
is it possible to track the funnel/goal if my checkout process goes through a 3rd party payment gateway, to which I have no admin access to modify the page code and add the tracking code, before it returns he user to a page on my site?
The whole process goes like: fill out order details on my site -> submit details to payment gateway (3rd party site) -> user fills out cc details -> payment processed -> user returned to my site.
Is this at all possible?
Thanks!
Thanks for the comment. If you track all your own pages you'll at least be able to track the return to your site so as long as a visitor comes back within 30 mins (default session time) you can still track them from the point they left to the point they returned - just with no visibility as to what happened in between.
However, I've had a lot of success working with third party vendors to get them to add the tracking code to pages provided for a client so it's worth sending them the snippet with a letter explaining why it is important. If you provide your snippet and ask them to tag each page in the checkout you stand a good chance of success.
Adam
The issue I had was because I only had the cross-domain tracking code on the page that took you to the 3rd party cart, but the documentation states that it needs to be on every page of your site and every page of the 3rd party cart to work correctly. If you want to talk about your setup, I do consulting on Google Analytics (see http://www.adamhowitt.com) so feel free to drop me a line if you would like my help.
Thanks for the comment!
Adam