Wait for iCloud and you should be able to re-download all of your purchased apps. However, there has been a couple of bugs with that because someone got charged 121 times for Lion. So it's a bit of a flip coin. Otherwise, it looks like your only option is to contact Apple Customer Service because they should have a record of your transactions on your ID. I had the problem too and they fixed it for me the next day.