Is there any block-cipher, format-preserving or similar encryption method with known cycle size? (without short-cut, with known source/runtime vars)
CAUTION: The following matches the requirement &quot;no short-cut in computing $m_i$ is allowed. It always either require the knowledge of  $m_{i-1}$ or $m_{i+1}$. Given two messages $m_i$, $m_j$ there should be no easy way to compute the difference $|i-j|$&quot; only with respect to an adversary not knowing the key. That goes straight against the added requirement that an adversary has &quot;access to runtime variables&quot;.

Well make an explicit construction from an $n$‑bit block cipher $E$ with the desired keyspace. Note $D$ the matching decryption.
Make a public partition of the blockspace $\{0,1\}^n$, assimilated to $[0,2^n)$ by e.g. big-endian convention, into intervals of size $c$ or slightly more according to the allowance for $k$. When $c$ is a power of two (e.g. $c=2^n/8$), that can be $2^n/c$ intervals of size $c$. When $\left\lfloor2^n/c\right\rfloor\ge(2^n\bmod c)$ [thus including any case with $c\le2^{n/2}$ ], that can be $\left\lfloor2^n/c\right\rfloor-(2^n\bmod c)$ intervals of size $c$, and $2^n\bmod c$ intervals of size $c+1$.
Define $h$ the bijection on $\{0,1\}^n$ that, to $x$ in a certain interval of said partition, associates the next integer in said interval if that's still in said interval, or the first integer in said interval otherwise. When $c$ is a power of two, that can be $h(x)\underset{\text{def}}=c\left\lfloor x/c\right\rfloor+(x+1\bmod c)$.
Define $f\underset{\text{def}}=D\circ h\circ E$. That is $f$ the bijection on $\{0,1\}^n$ with $f(x)=D(h(E(x)))$. That $f$ has the property &quot;After applying the function $c$ times (within allowance) it will result in $m_0$ again&quot; thought in the question, and has matching decryption $f^{-1}=D\circ h^{-1}\circ E$.

I conjecture that under the ideal cipher model for $E$, the resulting block cipher $f$ is secure when the number of (adaptive) queries an adversary can make remains negligible compared to $c$.
One slight implementation difficulty is avoiding side-channels in the implementation of $h$ and $h^{-1}$.