Admiral Miles Naismith appears in two books (The Warrior's Apprentice and The Vor Game) and two short stories before it occurs to anyone that he is the same person as Lord Miles Naismith Vorkosigan. How is that possible?
One of the many fooled people is Commander Ky Tung, who is a huge fan of Count Aral Vorkosigan and would presumably know about his Betan wife, nee Cordelia Naismith. On the Barrayan side, all of the counts learned about the Dendarii Free Mercenaries during Miles' trial at the end The Warrior's Apprentice, so you'd think something would have leaked out. Finally, as Miles rhetorically asks in Brothers in Arms (shortly before the connection is finally made): "Ivan, how many four-foot-nine-inch black-haired grey-eyed hunchbacks can there be on this damn planet?" While referring to Earth, people could have made the connection elsewhere, such as if any Barrayan expatriate or foreign spy joined the Dendarii.