Anime about a boy who collects memory fragments so that princess will remember him 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:

Tsubasa Chronicle




  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.