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 that are registered as Money Transmitters in all 50 states*. This isn't 10 Bitcoin related companies, this is 10 companies period.
* Well 47ish states (excluding states which don't have an applicable license).