Riverbed looks ideal but aren't they incredibly expensive? We looked at it years ago and I believe the necessary endpoints in our data center and in Singapore pushed past $140,000.

Riverbed (and all of the players in this space, really) are quite expensive, but this is where you get into the whole "Total ROI" argument for justifying the purchase.

Most companies depreciate hardware over 3 years. How much WAN/Internet bandwidth will you NOT use over the next 3 years, and how does that translate into upgrades you won't need to make?

There are also arguments for these boxes along the lines of "right now we use really expensive WAN links, but these boxes do end-to-end encryption too, so we can put the traffic on the Internet instead" but that opens up a few obvious cans of worms (and can of course be done without an accelerator with VPNs and whatnot).

Then you get into the more nebulous arguments that big bosses tend to like, such as "The average user makes Y XML requests per day to process X widgets. Each request takes Q seconds now. If we lower that to Q*0.5 with WAN acceleration, each user can now process N more widgets per day". Fluffy argument, but can have a big impact on business decision makers, especially if you can tie it to a dollar amount.

Note that WAN Accelerator salespeople are really, really good at coming up with arguments like this for/with you during the sales process.