There are things like MicroServices which you can focus on. I assume you are not the size of SAP and not in a position ask someone to throw them out when you walk in. Depending on the problem to solve, you can create plugins which integrate with existing ERP systems and provides specific value in a very specific domain. Pure API based is what I would recommend.
Of course, goes without saying that contacts on the inside are more or less a prerequisite.
enterprise sales is a different animal. for a startup it will be a serious challenge and one likely best tackled by working with a partner company that has already penetrated this company. The short answer is big enterprise companies are big and complex and need to serve a lot of different needs. Replacing an enterprise application is not trivial matter. The process is complex and time consuming and the contacts can be large - a small deal might be $200k and larger deals $100 million+ , so these decisions are not made quickly. I can assure you that the people you have spoken with who tell you that purchasing decisions (for enterprise applications) are made by a purchasing department do not understand how these decisions are actually made within their own company. Purchasing departments don't make these decisions. The IT department does not make these decisions. The process to implement or replace an enterprise app usually starts with an executive sponsor (VP, SVP, EVP, president, CXO, etc.). If the issue is important enough they will form an evaluation team which at some point will likely include IT and purchasing for tactical input. IT and procurement can kill a deal/project if they really want to, but they rarely have final approval/purchase authority. So to answer your question: how to navigate the maze: if you are thinking about starting a company to address this need/market the first thing you should do is find a cofounder or 2 who has extensive enterprise sales management experience (not only selling applications to enterprises, but building teams and negotiating, etc.). You would need to have a very compelling story and extensive enterprise experience yourself to build such a team, but it can be done. Here's a related post by Mark Susster. https://bothsidesofthetable.com/the-coming-shift-in-enterprise-software-17bdfd61ebb2#.y3ct4sn99
An alternative and much faster rout would be to team with a larger vendor who has the market presence and resources. You will still need to convince this partner company of your value add. If they are worth their salt they already know the company and the opportunity.