And in a follow up, MS just closed my case (without ever contacting me...) Some but not all of my history is back (specifically missing CleverPhoto, glƏƏk!, Hey DJ!, MetroTalk, Outsiders Extra's, Pirate Cat and Photo Lock. All of which were free some time this year)
Update:
Just contacted MS and this is what they said
'MS.: Ok, the bug has been reported and should be fixed by itself anytime from now.
Tom: ah ok, so you are telling me I just have to be a bit more patient?
MS.: Unfortunately, yes. There was a bug and many users are missing purchased apps or games from the Purchase history. I would advise checking again in a while. Please accept our apologies for the inconvenience.
'