An attack roll is randomness; a saving throw is randomness. If you don't want encounters that are completely trivial from a gameplay point of view, you must have an element of randomness.
The problem with high-level play (and D&Dg exacerbates this) is that encounters often _aren't_ random enough. It's easy to create a character with attacks that are impossible to resist by other characters. This occurs for a number of reasons, but ultimately, when your modifiers get up to +50 or +60 for attacks, AC and save DCs, the relative contribution of the d20 roll becomes insignificant. Thus either you win without taking a scratch, or you lose without standing a chance.
The topic of high-level campaigns being very hard to manage has been brought up multiple times. Everything has to be tailored to the party's abilities, if you don't want things to be a complete walkover (for either side). So far, I haven't seen anything that makes me think that Epic-level play will be any different -- in fact, it's probably going to be worse.
As to whether replacing a d20 with a d30 roll is the right solution, I'm not sure. It postpones the point where the die roll is superfluous, but brings with it its own problems, especially at low levels.
The problem really is the binary nature of most task/conflict resolution rolls -- either you succeed, or you fail. Some sort of gradated system might work better for high-level play. For example, instead of having the result of a disintegrate spell be either death or 6d6 damage, maybe you could have a range of possible results, depending on how well you made your save:
- death, if you fail by more than 20
- loss of half your hit points, if you fail by 11-20
- 6d6 damage (but not more than half you hp) if you fail by 1-10
- 3d6 damage (but not more than 1/4 your hp) if you succeed by 1-10
- no damage, if you succeed by 11+.
Something similar could be done for combat rolls and skill checks. This would be a major system redesign, obviously.