The first key hurdle is obviously to find the right company. RFI's and RFP's have been around long, and a very intelligent reply to them does not necessarily imply you would get the right set of developers to work for your project. A startup typically would not be a very 'big' account for most of the companies, and your probability of landing up with very good 'programming' talent is minimal. (I guess good programmers are in short supply at most places). At the end of the day, the developers on your project is what really matters.
Assuming, you are smart (and lucky) enough to have selected the right set of people for your offshored development project, still getting this relationship working across geographies, takes a bit of time. A fast and nimble startup, probably just does not have the luxury of time, assuming the product would change rapidly based on user feedback/market/competitor situation. (unless it was freakishly conceptualized in a brilliant way from the start itself)
In all, unless you have a relatively simple product in technical terms or a very well specified one, and have the luxury of time with you, only then look at outsourcing your development work.
One line decision maker: If you consider yourself a hacker, do not outsource your (initial) development. It's not for you, and high chance you would be left disappointed.