Is there an algorithm that allows verification that 2 encrypted or hashed bits of data are the same, given that I may only know half of the key/ salt?
I ran into a situation with a similar requirement, and here's the idea I came up with:

We don't use a conventional 'salted hash', instead to encode a user's password, we first hash it (optionally with the user's id, but without a salt) to form a value $h$, and then you select a random Elliptic Curve point $X$, you compute the point $Y = hX$ (where $hX$ is point multiplication), and then you encode store it as the pair of points $(X, Y)$.  To validate the password that the user enters, you again hash the password the user gave you, and then check if $hX \overset{?}= Y$; if it is, you accept the password.

This encoding is effectively one-way, given $(X, Y)$, it's infeasible to recover the password hash $h$ that would match it (assuming that we use a strong curve); this is the ECDLP problem.

$X$ effectively acts as salt; given a pair of encoded passwords $(X, Y)$ and $(Z, W)$, it is infeasible to determine whether they encode the same password; this is the dECDH problem.

And, finally (here's why it is of interest to you), it's updatable; at any time (be it once a year, or more often if we choose), we can select a random integer $r$, and replace $(X, Y)$ with $(rX, rY)$; effectively changing the salt we use without changing the password it matches.

Depending on your actual requirements, something like this might be adaptable to your situation.