Legacy code warts

Our vending machine at work takes all coins and paper money up to (and including) $20. I am fascinated by the change algorithm: if I buy something for $2.25, it returns the following sequence: $5, $5, change dump (combo of $1 and 25c coins), $5. Why does that last 5 dollar bill come out after the small change? Who programmed this thing and was it just some terrible change algorithm, or were they artfully covering up for some other system component, like maybe the paper money feeder is slow and it takes time to load up that third bill?
I've been trying to deduce the logic that's running in the background, and there are several options. In general, the approach seems to be to reduce the amount owed until it reaches zero. However, the order of operations seems odd. How could this output have been constructed? Suppose we're looking at just the function to output money owed.

Algorithm 1 (the simple one):
void ReturnChange(int cents) {
   while(cents >= 500) {
      Return5DollarBill();
      cents -= 500;
   }
   while(cents >= 100) {
      Return1DollarCoin();
      cents -= 100;
   }
   while(cents >= 25) {
      ReturnQuarter();
      cents -= 25;
   }
   while(cents >= 10) {
      ReturnDime();
      cents -= 10;
   }
   while(cents >=5) {
      ReturnNickel();
      cents -=5;
   }

   Assert(cents == 0);
}

This is simple, it works, and returns the fewest number of currency units needed. It will fail, however, if the machine is short on any denomination it needs. This is simple enough to fix up though:

Algorithm 1.1 (with error handling):
bool ReturnChange(int cents) {
   while(cents >= 500 && Return5DollarBill()) { // Return5DollarBill returns true iff it succeeded
      cents -= 500;
   }
   ...
   // and so on
   return cents == 0; // make sure the customer is happy. If not, ring a bell for service ...
}

So why on earth would someone not do it like this? And what might the code look like? I feel like I'm on some horrible conspiracy show. It's likely rather simple and rooted in the history of not this machine, but its ancestors. There was once a time when machines could only take coins or a $1, but for simplicity we just need to go back to when $5 was the cap. ReturnChange probably looked just like what I wrote above, except it didn't have the first while loop. Let's call this version ReturnChangeForUpTo5Dollars. Then some slick business guy realized that a lot of people don't carry small change around anymore because paying with plastic is so much more common. However, it's probably not unrealistic that someone has either a $5 or $10 bill, and the vending machine should support these. He pushed a task through engineering to update the machines with this new capability. Engineering looked at the building blocks they already had and how they could solve the problem:
1. Simply run the same algorithm over the now up-to-10-dollar amount. This gets shot down because if there's one thing worse than not getting a snack, it's getting 9 bucks in change.
2. Add the ability to feed out paper money. The 1 dollar case is already covered (and isn't useful unless a customer is using the vending machine as their strip club money dispenser), so they need to have it shoot out 5 dollar bills. Once they do this, they can simply wrap ReturnChangeForUpTo5Dollars to make ReturnChangeForUpTo10Dollars:

Algorithm 2:
bool ReturnChangeForUpTo10Dollars(int cents) {
   if(cents >= 500) {
      if(!ReturnChangeForUpTo5Dollars(cents - 500)) {
         return false;
      }
      if(!Return5DollarBill()) {
         return ReturnChangeForUpTo5Dollars(500);
      }
   }
   else {
      return ReturnChangeForUpTo5Dollars(cents);
   }
}

Notice the slightly odd code above! It has to account for the possibility of the machine being out of 5s. Thus if we try to dispense the $5 bill first and fail, we have no fallback case and need special case code to dump 5x$1, and if that fails ... in short, the whole fallback sequence has to be re-implemented. Like all good engineers, this guy found a way to re-use code that already existed, was tested, etc. Now of course they could have organized this a bit differently (and recognized that despite its name, ReturnChangeForUpTo5Dollars is general enough to return change for any amount), but the above is quite straightforward and easy to verify.

After the above update ships, they notice that there isn't a big uptick in sales, and specifically the number of 10s and 5s in the machines is about the same as before. Unfortunately Slick Biz guy forgot that most Americans (and counterfeiters) prefer 20 dollar bills ... so here comes Snack Attack 2.0! This time the engineers conclude that they don't need to invent the ability to dispense 10s because they can just use 5s and that's fine. They just need to update the return algorithm, and this time they're just gonna make it general so that they stop getting bothered about this:

Algorithm 3:
bool ReturnAnyAmountOfChange(int cents) {
   // we know how to return 10 bucks, so shave it down to that in $5 increments
   while(cents > 1000) {
      if(!Return5DollarBill()) {
         // if we have no 5s left, just give them a slot machine's worth of change. Sorry customer.
         return ReturnChangeForUpTo5Dollars(cents);
      }
      cents -= 500;
   }

   // and finish this off
   return ReturnChangeForUpTo10Dollars(cents);
}

Again, they could have just as easily updated either of the existing functions, but software engineers tend not to like to touch existing code. We're trained to be paranoid about breaking existing functionality. In this case, we'd need to re-test all less-than-$10 scenarios as well, incurring extra cost before getting to ship.

Of course I have absolutely no clue that this is what happened, but I wouldn't discount this theory!