from some quick search it looks like the online version is an area of active research. you dont mention the application area which might help to narrow down the literature search. one option is to look for an application area where theres the most or latest innovation. hence there is some application of incremental max flow in vision systems & some algorithms for it there; try Maximum Flows by Incremental Breadth-First Search at microsoft research labs. paraphrasing the intro to this paper, apparently for vision instances the Boykov and Kolmogorov algorithm does well & there are no known exponential time counterexamples although outside of the vision applications it might perform poorly. so it might be worth trying the B&K algorithm on your data & seeing how it performs & also the microsoft algorithm.
you seem to be saying that an incremental algorithm that is linear in the number of graph edges is not sufficient speed? but isnt that fairly high efficiency? how many edges are you dealing with? maybe the approach might be to decrease cost of traversing the graph if that is expensive or a significant factor (eg graph stored in db vs graph stored in memory)
here is an interesting paper that argues that while the nonincremental algorithm for max flow is in P the incremental version is NP complete. "To the best of our knowledge our results are the first to find a P-time problem whose incremental version is NP complete."
Incremental flow by Hartline, Sharp