What you're looking for is essentially a metagame, and it requires a few things, but not necessarily what you think. Let's look at your three assertions.
These all assume that you're going to play MtG in a campaign, and that there's going to be an institution for doing so. You've entirely overshot your goal by rushing to an implementation. Players can just get a booster pack when they do well from their own pocket. You can have a traditional GM handle the role of recording events and making sure things proceed, though the fact that the game's a little more complex makes group play difficult, as you could run into a situation where you have a bunch of simultaneous players. Fortunately, I'll cover that.
How to make it fit.
PvP play, of course, fits wonderfully into the feel of these games already. You don't need to worry about that. Random encounters, world-based narrative storytelling, and some of the whole "let's have X take your stuff" require a little more work. First things first, if cards are swapping hands, you need to have a criteria for how people will act. If the card is lost, stolen, or sold, what happens? If a card is introduced to the game, and it happens to be worth $250 on Ebay, this will come up.
Player versus GM play, however, would be necessary to handle stuff like a random encounter. You can simulate this by playing a creature according to patterns rather than necessarily using a whole deck for the GM; this ensures consistency between plays for fairness' sake but also has the upside of needing much less material. The world is also important, since you'd conceivably want this to function within a context of a setting, but if you're dealing with a bunch of people who aren't necessarily working cooperatively it gets a lot more difficult, and the best solution is pretty much just to summarize events at the end of the night with new narrative elements coming prior to and then after play but not necessarily during the games as they unfold.
Can it be done?
Yes, almost certainly. Look at BattleTech; it's a tabletop wargame at its core (and has an additional RPG component), but you can use persistent elements to simulate the course of a longer campaign. It's all about bookkeeping and basing things on what you actually need. If you think you need something, you'll add it, but it may just get in the way.
The easiest way to do this, of course, would be to digitize much of the rules keeping and stuff. With a collectible card game, this means you'd have to use proxies, digital cards drawn via RNG, or have someone with all the cards stored away, but you can just maintain a database containing every card in the system and who has it. Depending on how fancy you want to get, this can be a spreadsheet with a row for every type of card in play and a column for each player. Naturally, this gets huge quick, but it's a simple enough way to manage things. Side-note: Making everything digital is cheaper, especially if you just borrow cards and card descriptions from a database, which I believe M:tG has.
Let's look back at your one of assertions again; you assume that you want a limited card population. This isn't necessarily the case; if the GM holds all the cards and has to buy and track them all, then yes, and you certainly don't want people just buying their way to victory, but you can theoretically keep adding to infinity.
So how do we create a metagame?
Simply put, 90% of almost every metagame I've ever encountered is bookkeeping. 10% is actual content delivery; introducing a random encounter or something like that. If you've ever seen all the collectible card flash games out there, you'll get an idea pretty quick of how you could generalize something like that to Magic the Gathering.
Now, it's important to remember that for a deep, character driven experience in Magic the Gathering you need to equate the gameplay to the roleplay. This is why, for instance, you may see an occasional elite pilot in BattleTech or such but you don't see players "roleplaying" as an individual character.