Good good good GOOD ideas!
I like the idea of interconnected missions, a LOT. Missions that spawn different missions based on success or failure. That way, when you pick up a mission, you can get a breakdown of where it came from, what other players were involved in the events that created the mission and really feel like a part of the universe. On top of that, it makes it easy for everyone to feel like part of the main storyline since you can easily hook "mission origins" into whatever the main storyline/conflict/state of the game is.
I also like the idea of lasting local effects. Obviously changing the entire server fundamentally would be a waste of all the assets developed up to that point, but having, say, a faction change its whole aggro/faction settings permanently (hey, why are the Breen so aggressive all of a sudden?) could be interesting. Also, having, say the social or environmental conditions in a system or set of systems change as result of player actions (not just player combat) could also be very cool, and these altered states of these places could spawn a whole new set of missions indefinitely.
Note, that in order to do this, the mission system will have to be flexible and dynamic, as opposed to hard coded, so as not to 'waste' all the work that went into missions before the local area was 'permanently' changed.
I also like those mission ideas, escorting VIPs, Patrolling and exploring. The more varied mission objectives, the better. A cool thing would be having multiple missions at once... what do you do when you have a distress signal, but you're carrying a VIP?