Autorouters aren't very good because the algorithms behind them aren't perfect. Autorouting is full of little problems that are intractible. They can't be solved perfectly in a reasonable amount of time, or at all, in some cases, with a computer.
Autorouting is not necessarily an all or nothing thing. I route manually the critical nets and let the eagle autorouter do the rest. Works great for me (I don't care about the aesthetics of the tracks, just functionality).
This is why routing is accurately described as an art form, as there are no known algorithms that can do it better than an experienced human except in cases where the only directions that traces are allowed to travel are horizontal and vertical.
On the other hand it's cheaper to clone an auto router than an experienced human, for example for my home projects. ;-)
BTW, AFAIK, the complexity of auto routing is independent on the direction constraints. Once you figure out the topology of the tracks, there are efficient algorithms to generate any-angle, octilinear or rectilinear tracks subject to design rules. below is an example, (a) is the topology represented as rubber bands and zero spacing, (b) is any-angle with spacing enforced and (c) is the rectilinear design. Conversion in the other direction to topology is trivial.