It's about a boy who falls in love with a princess who makes a deal to save her life she must lose all memory of him. He has to go and collect memory fragments in the form of feathers and each one she remembers more.
I think I might have found it:
Synopsis (taken from the site itself)
During an excavation at the mysterious ruins in Clow Country, Syaoran discovers his childhood friend Princess Sakura appear on the site with wings that disperse into many feathers. As the feather's disappear to different dimensions, so does Sakura's memory. In attempts to save Sakura's life and restore her memory, Syaoran travels through to another world to find a solution. There's only one thing left he can do. Travel through to different dimensions to collect Sakura's feathers. Helping out with the quest is Kurogane, an exiled ninja from Japan Country who wishes to return to his world, the runaway magician, Fay, who desires to jump between each world never to return to his own and the white meat-bun shaped creature, Mokona.
I think it fits the bill almost perfectly. As the synopsis points out, he falls in love with Princess Sakura, who loses her wings and are dispersed into many feathers which go to several worlds/dimensions, all of this causing her to lose her memory. It fails to mention anything about the deal, but as for everything else, I believe it's a dead giveaway.