PG has this to say in his essay (http://paulgraham.com/start.html) :
"Start by writing software for smaller companies, because it's easier to sell to them. It's worth so much to sell stuff to big companies that the people selling them the crap they currently use spend a lot of time and money to do it. And while you can outhack Oracle with one frontal lobe tied behind your back, you can't outsell an Oracle salesman. So if you want to win through better technology, aim at smaller customers."
And it's not enough to have a product that solves a problem. BigCo never fixes things all at once. So whatever your product is, it'll have to work with innumerable poorly-documented legacy systems. Integrating with BigCo's existing, proprietary systems might take longer than developing the core of your actual product.
But the upshot is that BigCos are used to dealing with BigSoftwareCo that is just as slow and unresponsive in its development processes as BigCo itself. BigSoftwareCo doesn't want to fix our problems, they want to sell us an off-the-shelf product at a price tag that implies thousands of hours of dev work. So if you can show them that you can accommodate their needs quickly and without the usual obstructionism, technology dogmatism and nickel-and-dime-ing practices of BigSoftwareCo, there's definitely an opportunity to build a great relationship.
Many of those decisions do percolate to the CIO/CFO level for approval, but there is a world of difference between "purchase approver" and "decision maker". Directly targeting the purchase approver is often a very bad sales strategy.
Either way, my point was more about the fact that working day to day-to-day IT work won't give you the edge unless you have some sort of in with the guy/girl who ends up actually making the purchasing decision. It's also not as simple as this, as IT/Business organizations can be muddied with politics that don't always serve the IT personnel's productivity interest.
It also doesn't hurt to also get in with procurement. Which is another barrier I've found in "BigCo". Many large (Global 200) companies have a shortlist of companies they will work with and won't even entertain a conversation unless you are a certain size or have a pre-existing contract with them.
Therefore, many big company managers just head to amazon for their hardware rather than to the IT department. Part of the efficiency of ec2 is that you don't have to go through some salesrep and spend weeks going back and forth on price like you do when you buy pre-built servers (or way worse, data centre space or bandwidth.) There is no "vendor relationship" to manage, and "vendor relationships" add rather a lot of hidden costs on both sides.
My point is just that if you can solve the problem in a way that managers can plausibly justify an end-run around existing obstacles? I mean, you do need hype, and name recognition, but you can do it without a whole lot of high touch sales and "customer relationships."
Until you have a decent amount of employees and cash reserves, building any dependency on your product would be deal killing risk.
The assumption is you are likely not going to exist in 2 years.
I started off the in a similar manner, doing lots of consulting work. I know there is demand (in my case, its selling structured data), but however I am not too sure on whether the same demand would exist if I were to 'productize' my consulting work (ie. launch an api for structured data).
As one of the commentors, mentioned its really hard targeting the big companies and most small companies simply don't have the technical expertise to use an API (as in my case).
Many people will 'dream up' a new product/idea/concept, fall in love with it, and then try to build a company out of it. This has a much much lower chance of success. (great for including in a work of fiction, less useful when you're trying to convince people they need something they never heard of before). So don't do that.
But it also works for life, the 'Just Landed' app is a good example of something that I do infrequently, FlightAware made better (you can watch as the plane comes in) and this could be even better. But you have to have to consciously make the step of stepping outside 'living' your life and look at like as a process to be improved.
Some people do this naturally, others have to work at it, and some never get it. Diego's advice to talk to people and find out their pain points (everyone loves to complain) is a good way of seeing the process outside of that actors implementing that process.
- you really need contacts. As the OP points out, this involves working with them some time (in the inside, as contractor, selling to them, whatever). If you haven't, find a salesman who has the right contacts and experience: "don't call X, he's retiring next year and doesn't want to rock the boat with a new purchase. He'll just string you along. Call Y instead, he's new to the company and wants to prove himself - I play golf with him next Saturday".
- decision making at BigCo is at a frustrating, glacial pace. If you're used to the instant feedback of throwing something up in an app store or HN or whatever, you'll be disappointed.
- lots and lots and lots of meetings. Incredibly inane and the lead times are ridiculous.
- once you've proven yourself, it can be a real gravy train.