So now I have a new question: how do RPM-based distros manage without this feature.
I don't use RPM distributions, so I can't answer that question. In Debian, we've gotten along fine for a long time without a complete resolver  (the resolvers most users use are still incomplete) because the problem is so easy. The situations users usually run into can be solved with a greedy algorithm like your initial suggestion; with a few extra heuristics you can cover many other typical scenarios (such as the one I posted above). When users hit a situation that it can't solve, they either add instructions to force a resolution, or they ask for help on a mailing list and someone tells them how to add instructions that force a resolution.
The main impetus behind the aptitude resolver was that I wanted to improve the UI by providing user-visible explanations for the resolver's decisions and by allowing users to interactively guide the resolver towards a solution (for instance, by telling it that they don't want it to install a particular package version). I also wanted to add support for installing versions other than the current "candidate" . That I could make it complete at the same time was the icing on the cake. (but some very useful icing for people who have complicated dependency situations!)
 "complete" here means "able to find any solution to a dependency problem". Actually, aptitude only guarantees that it will find minimal solutions, but that's what you want (if "install A" solves a dependency problem, it's possible that "install A and install B" also does; aptitude might return both of these or only the smaller one -- ideally it would only ever return the smaller one, but I wasn't able to find a technique that would quickly minimize solutions).
 An apt term: the candidate version of a package is the version that apt will select to install if it's told to install that package. If versions 1, 2, and 3 of A are available and 2 is the candidate, apt-get install A will install version 2. The standard dependency resolver can't handle situations where a version other than the candidate is needed to resolve a dependency.