The very first sale was done before our recurring pricing was even built. We had a contact who sold video interviewing to One Laptop Per Child without a product. He was a sales guy trying to build a product, but was having trouble executing on the implementation (as programmers, this is probably an old story). He saw our product and said it was exactly what he was trying to build. He agree to split the revenue with us 50/50, if we allowed him to use our product for his clients. That was our first and last enterprise check, and this was before our product was even fully finished. The One Laptop Per Child interviewing went very well, and we were able to get some minor publicity out of it. At that point, we thought we had something big, and wanted to pursue our vision of a SaaS product, instead of doing pure enterprise with the sales person who found us. We were one of the first video interviewing products, along with Hirevue, and was sure there was a market out there. At first, this was true.
Our first enterprise sale on our own was Airbnb, and was relatively easy. A lead from one of their departments sent in an email, and after a demo, they signed up for our $500/month plan. We created that plan only to provide a contrast to our $99/mo plan, which we thought would be the primary seller. Turns out $500/mo is nothing for enterprises, and soon that's the only plan anyone ever cared about. The Silicon Valley startups in general were much easier to sell to. Wildfire Interactive (later bought by Google) was also an early customer, as was odesk, and a couple of other startup companies. They were all very easy to deal with. They were abnormal though, as we found out later.
The real enterprise sales experience came from more traditional industries. For our product, that meant mostly recruiting firms. No one used the free trial, and everyone wanted a demo. They wanted to speak to someone over the phone, and do several rounds of demos. The first was usually with a smaller manager or analyst in HR. Then subsequent demos would be head of recruiting or HR, or other senior executives. Almost every demo ended with the clients being impressed by the product, but no commitment. We did demos with some of the largest recruiting companies in the US, and with some of the largest retail firms in the US (head of Marshalls/TJMaxx, for example). In the end they went with a bigger company because they couldn't trust a couple of scrappy guys with their business, even though the product was good. Our pricing was also off-putting, because it was way too low. Low prices send a signal of poor support and poor quality to senior executives. $500/mo is a rounding error to them, and we probably would've made a better impression by asking for $10k upfront and $2k/mo and assigned an account manager to each client so they have a point of contact.
That taught us a lesson - if you want to go after enterprise, it's not really about the product. It's all about sales and hiring account managers and showing that you too are a big company. In that sort of field, you almost have to take VC funding to "act big".
The alternative is to do what Basecamp did which is become thought leaders in your field, but we really didn't love the recruiting industry enough to even attempt to do that.
I'm not sure if this is the type of answer you're looking for, as this is more of a failed enterprise company. I've talked to a lot of small companies who do enterprise sales, and the success stories I've heard always revolve around building an in-house sales team and ensuring a successful on-boarding experience for customers by way of account managers.
That costs a lot. For bootstrapped companies, that's just not possible.