Max sum cyclic path of fixed length in matrix
problem with this is that you can't be sure [which path] you can come from.


Indeed. So do it exhaustively for all feasible paths. That is, work on subproblems where you vary $t$ up to $K$, and store their results, at least for a little while. It should be possible to discard partial results corresponding to clearly bad solutions, and consume just $O(t^2)$ memory to remember the cells we should avoid.

Naively one could access a dense matrix opt by dereferencing opt[i][j]. To access the $n$th variant of a matrix with sparse edits applied to it, first probe a mapping to see if edit[(i, j, n)] exists, and if not fall back to dereferencing the dense matrix in the usual way. You may find it convenient to build up a path for the $n$th variant as a list of (i, j, value) tuples.

Additionally, we can decompose into the "outbound" and "inbound" sub-problems. Visiting a cell essentially sets that cell to zero, so each candidate outbound path gives rise to a new matrix. In the end the outbound path length will be $\frac{K}{2}$ and each new matrix gives rise to another $\frac{K}{2}$ inbound problems. The inbound solver would probe a hash map, and would add zero to the reward for any cell appearing in the outbound path.

Consider the Manhattan distance between current cell and origin. A decent heuristic for 1st stage search would be to make that distance strictly increasing on the outbound path, then strictly decreasing on the inbound path, which reduces the search space a little. Your idea about storing optimal values is a good one for further pruning the search space.

Please do keep us posted on your progress, especially on any pruning techniques that seem promising.