Can't you have itunes automatically download all your purchases, then you can still have that local copy on your computer and still use icloud backup? I'm guessing that's what happened.
Good point, it turns out you can get iTunes to download all purchased apps, I didn't know that.