Have you tried Scalyr? I am an employee at Scalyr and been in the infra space for quite a while. I think our logging product is the best I've used personally. Searches are actually fast.
Of course, we didn't try to negotiate, but it looks more expensive than Sumo. At one company we were spending around $600k a year on it, and it looks like you would cost closer to 1m.