What I've been pondering is how current major exchanges and transmitters such as coinbase managed to get all of these licenses when they first started up.
Simple ... they didn't.
As pointed out above there are only 10 companies in the entire WORLD you are registered as Money Transmitters in all 50 states*. This isn't 10 Bitcoin related companies, this is 10 companies period.
* Well 47ish excluding states which don't require a license.
And if you grab any newspaper and look at the bank ads, read the fine print, most large banks list the states where the ad is good for. Huge regional banks seem to only be able to operate in 10 states or so. Kind of a large barrier to entry. I guess spending billions on lobbying pays off for them and for the lawyers.