I haven't tried very hard to prove this or see if anyone else already has, but it "feels" right and I've tried running many simulations with the same rank lists and going through the applicants in random orders and 1) there is always a unique solution and 2) for a given set of lists, it's always the same.
No need to wonder about it. It's been proven:
http://en.wikipedia.org/wiki/Stable_marriage_problem
Note that the match without Prelims and without Couples is completely mathematically identical to the Stable Marriage Problem. Since in the match not all applicants are interviewed by all programs, and the number of spots and applicants are imbalanced, there will be unmatched applicants and unfilled programs at the end. But, without prelims and couples, there will always be one answer and it will be the same.
Note the section on "Optimality of the solution". This clear shows how the answer could vary, depending on how you define the "optimal" solution. Since the match uses an applicant driven process, in the example on the wikipedia page, if ABC were residents and XYZ were the programs, the solution would be the one were ABC get their first choice and XYZ get their third choice.
Adding couples changes the problem in a dramatic way. The problem now becomes "NP Complete" instead, which means that there is an answer, but you often can't come up with a simple algorithm that runs in a reasonable amount of time to find it. Here's why:
Think about what happens when the match is run. Let's say that your list is being processed, somewhere in the middle of the batch (i.e. half of the people have already been processed and have been "tentitively matched". The system tries to put you in your first choice. Turns out that your first choice is full, and the last person matched there is ranked #20. Sadly, you're #21, so you're out of luck. On to your next rank. Without couples, there would be no way in the future for a spot to open for you -- the only way someone could get bumped out would be if they were ranked higher than #20, and bump the person at #20 out (which wouldn't help you at all).
But, let's say that later on in the match process someone ranked at #5 is couple's matching with someone in radiology, and that person get's bumped out of their tentitive rad's match. Because of the couple's match, both spots are freed up. So, all of a sudden there now is a spot open at your top rank which you should get -- but you've already been processed. The standard algorithm only looks down your match list, since (without couples) it's impossible for something up your rank list to become open.
So, now you'd have to run through all of the applicants and tentitively match them, and then run through them all again to see if spots have opened higher on rank lists (and of course everytime you change something, you have to start all over again to see if other matches need to move). This is why couples make the match much more complicated. It also does create a situation where the order that you process applicants might result in a different answer. In order to minimize this, I expect the NRMP processes the couples at the end -- that minimizes the amount of disruptions. Note that being run last doesn't in any way hurt your chances to match -- you'll simply bump someone else out.
Note that this was studied, and the effect of running the match in a "different order" made a minimal difference -- using 5 years of data with 12000+ matches, the largest difference was somewhere around 4-5 spots, and in most cases was lower than that.