How about when you hit a certain XP, (Enough for the license) a new mission opens up in nation sectors.
These would have challanges and objectives suitable for the license, so:

combat you would have to outrace a opponent.
Light you'd kill a Speical assault craft (Tycorp, etc)
Heavy you'd kill a Speical heavy craft (guardian, etc)
Trade you'd have to make a certain amount of money within the time limit
and Mining you's have to find a hidden roid in a sector with speical minerals

I think this would add a whole new dimension to leveling, taking away the power gamers edge.

minus the time limit thing, isn't that how it is now? As you increase your combat license you have to progresively kill harder and harder bots? They just stick it all into a single "Advanced Combat Mission" title, but the targets change.

There was a post somewhere else that mentioned having special npc's that were say… named pirate ships, that could be used in special bounty missions. I think that would be sort of what you are talking about. Ace pilot missions, take out the reb barron or something like that.

As for timed missions for trade, I think some timed and some not timed would be a great way to mix things up a bit.

There definitely needs to be missions for mining. I know this is a new addition to the game so let's see what they add at there next addition. =)

Our current rudimentary mission tree is more of a shrub at the moment. A much more complex mission tree is in the works.