There is an encounter at the South Church which allows any cursed investigator to discard his curse. Does this apply to Rex as well, who can't discard his curse except by being blessed?

That's a good one. I'm not so sure about the correct answer; but I'd say no, he has to keep his curse. Basically, the encounter says "If you pass, then you stare up at the stained glass windows, see the light shining in through them, and realize that your troubles aren't as bad as you thought they were". You have the idea of a divine intervention relieving a little the troubles of your buddies when cursed, but Rex has not a "normal" Curse. It's rather a persisting one, so I'd say play it literally: if it's not clearly said "you're blessed", then you keep it. But it's just the way I'd play this situation.

I'd say he can't discard it. His sheet says he may only lose his curse if he becomes blessed.

Likewise for the King in Yellow encounter that says blessings become curses and curses become blessings (in my view anyway): he did not obtain a blessing to nullify his curse.

Not to hijack the thread, but the terms "Blessed" and "Cursed" are, in my opinion, the most infuriating unclear terms of all the Arkham vocabulary, simply because they can be used to mean the receiving of a Blessing or Curse or the state of having one. For example, I agree with you on the effect of that encounter, Tibs, but it could easily be argued that it negates either one (if you have a Blessing, you are Cursed and discard the Blessing; if you are Cursed, you are Blessed and discard the curse). Similarly, with Rex Murphy's story, the phrase "Rex is Cursed and cannot be Blessed" could be interpreted to mean that he cannot actually have a Blessing or that he cannot receive one (if the former, he could use a Blessing to get rid of his Curse; if the latter, he could not).

The actual encounter says something like, "realities are reversed. If you were blessed, you are now cursed; if you were cursed, you are now blessed." This means that you do not merely negate the card you have by obtaining the opposite (it would have just said to lose your blessing or curse); rather, you switch completely to the "opposite" status. Therefore, Rex can't lose a curse that way. Though if he happened upon that card while blessed he'd be in for a nasty surprise.