You want to be very careful with this, as you can end up classified a money transmitter and have to comply with a whole bunch of painful regulations. Just search for PayPal chained payments or Amazon's equivalent, it will do exactly what you need.
So, the realistic options left imho are ACH using something like AmazonPayments and sending out checks, which has its issues. Unfortunately there simply aren't as many options for paying money out as there is taking it in.
Btw my startup is Sponsorist.com, currently taking $ in through Stripe and sending out as checks. For now. :)
Checks are fine but as a foreigner they seem really clunky and don't work once the company has a greater reach. Shame PayPal flagged you so early on.
I wonder how many other startups are in your position.
Food for thought.