Where technology can help today
Some of these barriers are political issues that technology can't solve; at best it can work around them, such as through pattern matching to narrow down potential patient ID matches. But there are technology efforts under way to help.
The two largest medical providers in the United States (the Defense Department and the Veterans Administration) now have a common backbone, EHR interchange format, and connectivity APIs, based on a software-oriented architecture (SOA) services approach -- a once-hot notion well suited for dealing with federated systems. Their populations have a lot of overlap, so the integration makes sense. Dealing with just two providers means the name-matching is easier than in a multiprovider system, such as across a state or across the country.