There is a precedent for doing it legally, Paypal, Facebook Credits, etc are all digital currencies. They do it by getting licensed as a money transmitter and complying with all AML and know your customer laws. It's an expensive and long process but people are able to do it. Not sure I fully understand the last two bullets. In general I think you're right that this startup will have larger legal challenges/costs than most but building something that is 100% above board and shows you're making a good faith effort to comply/do the right thing buys you a lot of good will. You want to be YouTube, not MegaUpload.