I just found an Android web store called AppBucket. When you pay a subscription, you can download non-free software from their service. The site doesn't really explain what kind of deals they have with the developers of these non-free apps, but I guess they buy software once and then sell it to all their subscribers, which seem a bit illegal. What do you think?
It is very tempting to subscribe to this service, as my Android market in my country has just free apps available. But I don't want to break the law!