The Time Traveller's Wife immediately popped into my head when I read the title..and then you'd already listed it. Such a beautiful book.
The Twilight saga by Stephenie Meyer is about as non-traditional of a love story as it gets. (I don't like vampire books, but loved the story in these). They are classified YA, but still great stories about an unusual romance. Ditto for her book "The Host". It falls more into the SF range, but is a great and unusual love story.