For the first part of your question, I think the answer is a combination of three things: (1) Bigger companies have leverage to negotiate better deals due to volume. (2) Some of these companies are also taking bookings from outside the US for people traveling to the US (either directly or through affiliates). This means that they also have income in other currencies, so they may not actually be making as many wire transfers as you think. They simply keep a bank account in Europe, for example, in Euros to receive and send money in the Eurozone as needed. They balance the exchange on their books internally in this case, without actually sending funds through the international banking system. Similarly in other parts of the world. (3) These companies are not going to make a wire transfer for every transaction, in any case. They are going to transfer big sums of money to an account abroad to balance things on a longer-term basis (weekly, month, etc.) Then they will make individual payments to service providers out of the overseas account in between these larger, international transfers.
For the second part of your question, I think there's probably no way for a new business to get the advantages of scale unless you've got significant capital backing your endeavor that would make it plausible that you'll be transferring in scale. I don't see any reason in principle that the new company could not establish bank accounts abroad and try to execute the plan outlined in #2 above except that it would require some set-up costs to do the proper paperwork in each country, probably to travel, and to initially fund the various accounts.