Well, the structure is very informal-- like a transcription of spoken English. If I were writing it, I would treat OK as the interjection it is, and use m-dashes:
I thought there may be a change in the address, but-- okay-- you are still at the same location.
I would definitely use 4, as reported speech for past time implicating a doubt. See Swan.
However, the practical grammar is in a slight mess in this area:
The New York Times gives:
"thought there may be" 3 Results to me, this is is past time extended to present validity (the thing/situation which I thought of then, is still valid now)
I agree with Marius that "might" is better than "may", because we see that what the speaker thought is not still valid. However, "might be" or "might have been" both sound OK to me.
My intuition when I thought about this issue: in the strict sense of "may have" and "might have" mean, they are a lot better than "may" or "might" because, with reference to the rest of the sentence, the speaker's thought is not still good. "May have" and "might have" refer to only the past.