A "weak solution" demonstrates perfect play from the initial state and merely implies the existence of a perfect strategy for the entire tree of game states, but, crucially, need not actually produce said strategy. Doing so would be a "strong solution."
An "ultra-weak solution" is even less. It gives the win/lose/draw outcome of the perfect strategy, without producing that strategy, nor even producing the game of perfect play from the initial state.
This is all covered in the second paragraph of the paper's introduction.
And if a strategy for perfect play only from the initial position is a strong solution, then what do you call the even more strongly solved case of a strategy for perfect play from any position?
The second paragraph of the paper isn't super specific about its definition for "weakly solved", but I read it as agreeing with my statement. It also calls checkers "weakly solved", a game for which a strategy to beat any possible move is known.
An "ultra-weak solution" is even less. It gives the win/lose/draw outcome of the perfect strategy, without producing that strategy, nor even producing the game of perfect play from the initial state.
This is all covered in the second paragraph of the paper's introduction.