In response to your edits:
>but they can't get more flights because of their record
The Air Force required 3 successful flights in the exact configuration the Air Force would fly. SpaceX provided the "record" as stipulated by the Air Force, which nevertheless committed to a large block-buy contract with ULA. By the Air Force's own standards, the billion-dollar subsidy is not necessary for their needs-to-get-to-space payloads.
Also, "the other companies" is just a single supplier, ULA.
But sometimes we would see unimaginative stuff like a specification of the LED layout on the front panel or very specific weight restrictions that happened to fall between our hardware and the preferred vendor.
In the government's defense, though, the system is set up to combat this tendency, at least for smaller contracts. When I was on the other side (having left the vendor to work for our civil service customer) we would routinely get pointed questions from the purchasing people regarding this or that line of the RFP - was it really required, or were we trying to wire the contract?
and my understanding that this supply is limited to the what had already been manufactured long time ago. Beside the inventory issues, one can easy imagine Putin saying "bad Americans, no more gas ... err... rocket engines for you"
NK-33 - from which AJ-26 are made - aren't manufactured today. It's a question if the manufacturing will restart. There are a few tens of them in US. Orbital Sciences has that question in the middle of their table, or close to it.
Russian-American relationships in space trace back to at least 1975, deep Cold War. We're not at that state of affairs just yet. As somebody mentioned on The Space Review, ISS is a front-runner for Nobel peace prize, so let's not jump the gun too early. It doesn't seem to be too desirable for Putin to close that particular relationship.
I used to intern for a company trying to break into aerospace software---not hardware, just tracking and modeling. At the time, they faced a nearly-vertical climb into the market to get around the big names in aerospace; they couldn't sell to them directly (the people involved in the purchasing decisions were the people who would be getting downsized if the software proved to be as good as advertised) and they couldn't sell to the Air Force (it's basically nearly impossible to get into an AF contract cycle if you haven't been in an AF contract cycle).
Their break-in point was the US Army; at the time, the Army had a relatively small air asset capability (relative to the other branches), but a sudden need to know what was up with the GPS constellation AT ALL TIMES relative to their land and air deployments. The company was able to get face-time with the Army reps because the regular aerospace names wanted to sell them software that came at a price-point that usually bundled a shiny new fighter jet or stealth asset with it, and they weren't willing to drop their prices because they didn't want their regular Air Force customers asking "Why is the Army getting this software for a tenth of the up-charge you quoted us when we closed this whole contract last year?"
Sadly, that was years ago and I have no idea of the shape of the market now. My only other data point is the portrayal of the aerospace industry in the movie _The Aviator_ and the observation that it hadn't changed much between then and the early-21st century. ;)
I guarantee there will be a congressional committee hearing about this very soon. Reminds me of what Howard Hughes had to go through to break Pan American Airways' legal designation as the United States' sole international carrier. Most portray Elon M. as a the new "Steve Jobs"; wrong I live in Nevada and an early study was of Howard Hughes. Elon M. is a modern day Howard Hughes. Once you understand that, things fall into place.
These are the relevant rockets and their first stage engines that fly from US soil:
1) ULA Delta IV: US made RS-68 (new).
2) ULA Atlas V: Russian made RD-180 (new).
3) SpaceX Falcon 9: US made Merlin-1 (new).
4) Orbital Sciences Antares: Soviet made NK-33 (decades old, now refurbished in USA).
Also to match costs, you have to look at the payloads and the distance to space.
Falcon 9 - $56M - 4.8 metric tons to GTO
Falcon 9H - $135M - 21 metric tons to GTO
Atlas IV/V - $160M - 7 metric tons to GTO or 21 tonnes to LEO
Ariane V - $200M - ? metric tons to GTO
http://spaceflightnow.com/falcon9/007/131124commercial/#.U1q...
These other companies justify the higher price because they have a better track record. If you're a military customer and your payload needs to get to space, you probably will choose the "safe" bet. Its a catch-22. SpaceX needs more flights to prove their record, but they can't get more flights because of their record.