Delaware is somewhat of a specialist in corporation organization, and a huge portion of the state's legislative and judicial resources are invested in being the venue of choice for incorporating a business. That's why the taxes on individuals living in the state are so low, they get a lot of income from corporate taxes and filing fees.
If you are incorporating somewhere solely for the purpose of doing business elsewhere, a Delaware C corporation will definitely do the job, in the same way that a rocket propelled grenade can technically fulfill the same role as a flyswatter.
If you have a functional business, and don't need investor money, an LLC will work just fine. Delaware, Nevada, and Wyoming are the most popular states to register an LLC, but by now, all states offer their own flavor of a limited liability partnership-based company.
A New Mexico LLC does not require annual reports or fees, does not require naming your principals or filing much more than just the articles of organization. The filing does not have to be done by a member of the LLC. You just need to maintain a registered agent somewhere in the state, and that is pretty much the only requirement for staying in good standing as far as the state is concerned. You literally just need to hire a registered agent, fill in a very simple form, and pay $50. No lawyers are required (unless you hire one as your registered agent). If you are not doing any business in the US, and none of your LLC members are US persons, I don't think you need to concern yourself with US taxes. You register your foreign corporation wherever you are doing business, and if they call up the New Mexico Secretary of State, they will say, "yep, we do have an LLC registered in that name".
If you want a US bank account, you will need an EIN from the U.S. federal government, which can also be done by a nominee having no other association with your company.