Your objection to more complete is reasonable. It is probably not worth troubling with in colloquial or semiformal contexts, but in an academic context with any pretense of rigor it is quite properly avoided.
The simple solution is to describe the superior solution as “more nearly complete”.
That, however, is the least of your problems. You should not use the term complete at all unless you define quite precisely what you mean by it. Without more knowledge of what it is your solutions solve and what metrics govern your attribution of a greater degree of completion to one than to the other, it is impossible to say how you ought to express this; but by way of example:
The solution put forward by Nishiyama and Koenig (2010) is similar to that of Michaelis (2008), but is more nearly complete in that Nishiyama and Koenig claim to account for all perfect constructions, while Michaelis accounts only for resultative perfects. Neither solution, however, accounts for all uses of perfect constructions; in particular, neither gives a wholly convincing explanation of the drift in US usage away from use of the present perfect in continuative perfects.