Agree on ship early/ship often, but most of the startups I've observed (granted, a small sample) didn't skip customer development because potential customers wouldn't call them back. By and large, I think most folks are willing to sit down with you for a cup of coffee for 30 mins and talk about their needs and how your product could help, especially if you make it clear up-front that this is not a sales call.
YMMV, but we've had great success with just sending an email or picking up the phone and asking people if we could chat for a bit.
Agree that most people who skip CD are doing for lack of trying ;-). I think the ease of gaining access depends largely on the target customer profile. Consumer, even SMB targeted stuff by definition has a large number of potential customers compared to the Enterprise. Additionally their barrier to purchase is much lower than the Enterprise, therefore the signal from your 30 minute cup of coffee is much stronger. It's a trickier proposition with Enterprise customers, but I guess that's why the deals are bigger.
YMMV, but we've had great success with just sending an email or picking up the phone and asking people if we could chat for a bit.