It could be stream based (address and port), and use a LRU cache with a planned capacity of 5 minutes, to decide on which interface to use. Sure, it is more complicated, but anything you add increases complexity.
not so. right now our multihomed web gateways need a full routing table. that's pretty complicated, for my operator and for my customer's providers. we're shortly moving to an "interface default" such that all inbound streams will have their outbound route chosen as the incoming interface's default, and all outbound streams will get a "round robin default" outbound route that will then be rebound to the SYN-ACK's incoming route, in case the original source route is better-reachable by "this" destination via some other interface, a not uncommon case these days. this adds about 2 pages of code to the kernel. but it's a lot less complex than taking a full routing table from multiple providers.