Your conclusion is correct.
Medical records cannot be encrypted so long as demographic data must be stored in plaintext. Otherwise how would we do record matching (linking) across heterogenous systems?
The fix is to use universal identifiers. Once you moot the record matching problem, you can use translucent database techniques to anonymize patient data.
I don't expect the USA to adopt an official centralized universal identifier for people any time soon. And none of the 3rd party solutions (NSA, LexisNexus, ChoicePoint, Facebook, etc) are acceptable, for various reasons.