Whom they believe is the missing brother.

Yes, as long as people know who "the missing brother" refers to.

We rarely use "whom" (you see I didn't, just above) but you have used it correctly.

With all due respect, I would consider whom incorrect. The relative pronoun is the subject of the relative clause: They have found a man who they believe is the missing brother.

CB

I had to think about that one. You're right, CB, but I really want to use whom there.
"They have found

I saw this in Using English and see others also feel "who" is correct.

I read it exactly as Blue Jay: they believe him to be...
I guess you can also read it as "they believe he is..."

I would totally agree that "they found the man who is..." requires "who" but with the "believed" part in there, I think you might be able to go either way.

Yes, its the "they believe" part that threw me off too. I had to do the he/him test on the sentence to see that CB was right.
Who do they believe he is? They believe he is the missing brother.
Whom do they believe him to be? They believe him to be the missing brother.

I just can't stop "hearing" they believe him to be.

But I agree with you.
(I'd drop the pronoun entirely.)