I think Athelstan makes some good points, actually. At the very least there are things that concern me about the xp system too.
As a simple example, the DMG states (something like) that xps should be calculated based upon the creatures base CR and not modified for the parties circumstances e.g. are they fresh, are they knackered - the latter party will have a much harder time of the encounter.
Some possible thoughts I've had (or seen) about awarding exps.
1. Assess challenge from the results.
For each encounter decide how easy or difficult was it for the PC's? Did the creature fail its first save and disintegrate on round 1? Perhaps that was a minor challenge/resource drain and calculate xps as CR-2. Did the creature kill one party member, take two down into negatives and leave the last person on single digit hp before it was taken down? That could be considered a very serious challenge and be worth CR+2 (in each case CR == average party level here, and is just used for assessing xps.)
i.e. use monster CR when planning encounters to give you an idea of the difficulty of the encounter vis a vis the players, but award experience on the basis of how much hassle the party had overcoming the encounter - did it use up 20% of resources? Then calc xps as if CR==level. Did it use less paty resources? More? Calculate xps as appropriate.
2. Provide standard xps for all
This is basically in the DMG. Everyone gets 50xlevel xps every encounter, or Xxlevel xps every adventure or everyone gains a level every three adventures etc.
3. Provide xps for time alive
More radical - assume that every person in the campaign world gains xps just for breathing. If basically sedentary/commoner type it might be 1xp per day, nobles, professionals and people with responsibility 3xp per day, adventurers 5xp per day. This doesn't yield a constant rate of progress through the levels, and would put a stop to the teenage archmages which crop up in 3e

It would also give meaning to downtime etc. I don't imagine this would be terribly popular though.
4. Provide xps only for training
Another radical option. Nobody gains xps just for doing stuff, they have to bring their money back to the city or their den or wherever and then spend time and money on training themselves. Whatever conversion rate is appropriate can be determined by the DM - e.g. 1gp = 1xp. The limiting factor is that training takes time, and you can only spend level*100gp each week, maximum. Thus it takes time to convert xps into money.
5. Divide generic rewards into "level of challenge" and "effectiveness of play"
This idea comes from someone whose name I can't remember and whose website I can no longer find

Basically there are two things to consider when assessing xps rewards
a) level of challenge
minimal level*50xps
minor level*100xps
standard level*150xps
major level*200xps
incredible level*250xps
b) effectiveness of play
minimal level*50xps
minor level*100xps
standard level*150xps
major level*200xps
incredible level*250xps
(I've probably got the figures a little wrong here).
In Aethelstans original example party A might get standard level of challenge, major effectiveness (netting a total of 350*level xps) while party B get standard level of challenge and minimal level of effectiveness (netting a total of 200*level xps).
Fine tuned to ensure that PC's gain levels at a rate appropriate to the campaign I could see this latter system working particularly well to handle the kind of situation he describes.
Cheers