[Take three, re-simplified, and strengthened]
Improving on the line of thought in [that other answer][1], we will craft two efficiently computable functions $H_1$ and $H_2$ each accepting two arbitrary strings as input, with output a fixed-size string, say 512 bit; and (I conjecture) indistinguishable from a random function except for this superset of the desired property:
$$\forall(i,j)\in\{1,2\}^2,\forall(s_1,s_2,x), H_i(s_1,H_j(s_2,x))=H_j(s_2,H_i(s_1,x))$$
We'll use as building blocks three 512-bit [PRFs][2] $P_0(m)$, $P_1(m)$ and $P_2(m)$ accepting an arbitrary bit string, and one 512-bit [PRP][3] $E(n)$ with $D(m)$ its reverse function, such that $D(E(m))=m$.<br><sub>We can build the PRFs as $\mathtt{HMAC}_\mathtt{SHA512}(k,m)$ and three arbitrary distinct $k$. And by this [famous result][4] we can build the PRP as the four-rounds [Feistel cipher][5] with round functions $\mathtt{HMAC}_\mathtt{SHA256}(k,m)$ and four arbitrary distinct $k$.</sub>
For $i\in\{1,2\}$, and $x$ restricted to 512-bit strings, we first define
$$\widehat{H_i}(s,x)=(P_i(s)+x)\bmod{2^{512}}$$
The desired property $\widehat{H_i}(s_1,\widehat{H_j}(s_2,x))=\widehat{H_j}(s_2,\widehat{H_i}(s_1,x))$ is met, because addition $\bmod{2^{512}}$ is associative and commutative. However these $\widehat{H_i}$ make rather poor hash functions. In particular, the output is linearly malleable using the second input; and we'd want to waive the restriction on the second input being 512-bit.
We need added camouflage. For $i\in\{1,2\}$, define $H_i(s,x)$ as $E(\widehat{H_i}(s,D(x)))$ when $x$ is a 512-bit string, and $E(\widehat{H_i}(s,P_0(x)))$ otherwise.
The desired property $H_i(s_1,H_j(s_2,x))=H_j(s_2,H_i(s_1,x))$ is inherited from the $\widehat{H_i}$, and the $H_i$ functions appears much like random oracles, except for consequences of that property, to someone ignoring the PRFs and PRP.
By querying the functions/oracles $H_i$, it seems impossible to learn something on the value internally added, or internally add 0, other than by chance. Computing $H_1(s,H_1(s,\cdots H_1(s,H_1(s,x))\cdots))$, where $x$ is a 512-bit string and there are $2^n$ iterations, has odds only $2^{n-511}$ to return to $x$; if we had used XOR instead of modular addition, we'd have $H_1(s,H_1(s,x))=x$.
---
Open problems:
- Can this be meaningfully proven secure (or broken)?
- We do not need a full group operation (on the contrary, the neutral element and existence of an opposite are a risk), any commutative [semi-group][6] will do; is anything more suitable than $\mathbb Z_{2^{512}}$?
- Is $H_i(s_1,H_j(s_2,x))=H_j(s_2,H_i(s_1,x))$ a consequence of $H_1(s_1,H_2(s_2,x)) = H_2(s_2,H_1(s_1,x))$?
- If not, can we make a construction with only the originally asked property?
[1]: http://crypto.stackexchange.com/a/3107/555
[2]: http://en.wikipedia.org/wiki/Pseudorandom_function
[3]: http://en.wikipedia.org/wiki/Pseudorandom_permutation
[4]: http://dx.doi.org/10.1137/0217022
[5]: http://en.wikipedia.org/wiki/Feistel_cipher
[6]: http://en.wikipedia.org/wiki/Semi-group