[Note: I'm the co-founder of OpenCorporates, which along with our reconciliation service for OpenRefine, has been kindly mentioned by several of the answers, but I've tried to cover some of the general issues here, using our experience, rather than suggesting we've got all the answers]
This is a really difficult problem because in general it requires more than just string algorithms, and also because of the underlying question of what you are matching.
So first, what will you be matching the normalised strings to? If you're matching them to companies (legal entities), OpenRefine is really great for that as long as it's for jurisdictions that we have in OpenCorporates (we have about 30 of the US states, for example), or it's matching the names against entries in Wikipedia, using Freebase. I'm not sure of the matching algorithms that Freebase use, but we do all the usual things such as you've got with your ACME examples.
With the Walmart examples, it's rather more difficult. In part this is because sometimes these normalisations would lose information that is helpful in matching to entities. Take the hyphenation issue for example, and say you were searching for Wal-Mart Limited. If you search OpenCorporates on the web interface (which is pretty liberal in what it returns, and for the sake of this example, let's say we're limiting to companies in the UK, and this is what you get:
- CREDITS INVESTMENTS LTD (United Kingdom, 16 Feb 2007- )
- DOS-MART (UK) LIMITED (United Kingdom, 18 Feb 1999- )
- GEORGE SOURCING SERVICES UK LIMITED (United Kingdom, 2 Jun 2000- )
- WAL MART LIMITED (United Kingdom, 5 Jan 1999-17 Sep 2002)
- WAL-MART LIMITED (United Kingdom, 12 Apr 2006-31 Mar 2009)
- WAL-MART LN (UK) LIMITED (United Kingdom, 3 Feb 2000- )
- WAL-MART STORES (UK) LIMITED (United Kingdom, 26 Apr 1999- )
- WAL-MART STORES LIMITED (United Kingdom, 18 Mar 1994-10 Jul 2001)
Look at the fourth and fifth entries and you can see the problem. One has a hyphen, one doesn't. It's also worth looking at the first three entries, and these were returned because their previous names matched Wal-mart. There are also lots of other cases where normalisation brings false positives.
So although we do some normalisation, we also score against the non-normalised search term in our reconciliation API. We also are increasingly using other attributes of the companies, scoring current companies higher than dissolved companies (company names are often used by unrelated companies over time), unless a date is supplied in which case we return the company that was called that name at the given date.
Finally there's the question of what do you want to match? With Walmart, maybe it's 'obvious', but in general it isn't, even with something like "Tesco", the world's second biggest retailer (after Walmart), which could match several unrelated entities around the world, including the US.
That's why when we're matching a dataset using OpenRefine and OpenCorporates we do a first pass, limiting to a jurisdiction, passing dates in where we can, and then automatically reconciling to those entities which have a high score and where there's just one high scoring result returned by the API (there's some cool filtering in Google Refine to do this), and then progressively go down the scores, sometimes using the ability to do live reconciliations, to match the ones with no match, or with ambiguous results.
Because we use the service internally we're constantly finding 'edge cases' (that aren't so edgy), and improving the matching. People who've used it and the proprietary DBs reckon OC is very good. However, we can see there's massive of room for improvement. We're now doing more normalisation for non-US/UK company forms (e.g. GmbH and SA/SARL), and playing around with transliteration, and when we launch company hierarchies, there's obviously potential for assuming that by Walmart/Wal-mart you mean the company at the 'top' of the Walmart tree.
Hope this helps.