I'm looking for a specific Middle-earth-based fanfic...

I remember reading bits and pieces of it many years ago, but for the life of me I can't remember the title. It was a romance story about a Gondorian soldier who falls in love with a Haradrim woman (that's right, a straight, intra-species relationship in a LotR fanfic; wonders never cease).

Does anyone have the foggiest idea what I'm talking about? I'm a sucker for the "lovers from different worlds" genre, so I enjoyed it.