Fra slutningen af 1950’erne fik Carl Madsen en ny klientkreds, der også efterspurgte hans særlige politiske og juridiske kundskaber – de nye kommunistiske stater i Østeuropa. I de første fem år efter befrielsen var kontakterne imellem de danske og tyske kommunister i det store hele sat på pause. Det skyldtes det generelle kaos i Østeuropa kombineret med stærke antityske strømninger i DKP (det danske kommunistparti, red.). Men op til og under besættelsen havde Carl Madsen haft tætte sociale og politiske relationer til de tyske kommunistiske emigranter, der var flygtet fra Hitlers regime, og hvoraf mange fortsatte de politiske aktiviteter i København. Grundlæggelsen af det kommunistiske DDR i 1949 betød, at en række af disse tidligere eksilkommunister nu gjorde karriere i den partielite, der regerede den nye østtyske nabostat. Historiker Michael F. Scholz har vurderet, at relationerne fik væsentlige konsekvenser for det lille danske broderparti:
»Iog med at man fik en vidtgående udenrigspolitisk suverænitet i 1954/55, blev det et vigtigt mål for SED (det østtyske kommunistparti, red) at ophæve DDR’s internationale isolation. Også i nabolandet Danmark skulle der ved hjælp af DKP skabes kontakter til DDR-sympatisører, og der skulle drives image-pleje som første trin på vej til folkeretslig anerkendelse«.
Omvendt understøttede det østtyske SED på afgørende vis det svage danske parti – ikke mindst efter bruddet med Aksel Larsen og tabet af de resterende folketingsmandater i 1960. En af de danske kommunister, der i særlig grad kom til at optræde som DDR’s utrættelige forsvarer i den danske offentlighed, var Carl Madsen. Selv om han først for alvor selv udnyttede de gamle østtyske venskaber og netværk fra slutningen af 1960’erne, hvilket var en forudsætning for udarbejdelsen af bogen ’Flygtning 33’, så repræsenterede han allerede fra begyndelsen af 1960’erne østtyske interesser i Danmark. Følgelig blev han behandlet som en prominent dansk kommunist på lige fod med Ib Nørlund, Alfred Jensen og Ingmar Wagner, der opdyrkede tilsvarende politiske netværk i DDR.
At Carl Madsen både var en markant offentlig stemme og en dygtig sagfører, gjorde ham attraktiv som en selvkørende dansk kulturdiplomat, der havde spidskompetencer, som kunne sættes i spil i det erstatningsdiplomati, der gik forud for den danske anerkendelse af DDR i 1973. Carl Madsens østtyske relationer skulle blive intensiveret helt frem til 1973, ligesom der udvikledes tætte bånd til de polske og ungarske ambassader. Men væsentligst var de østtyske forbindelser, der både gjaldt et stort netværk i selve DDR og en række semiofficielle relationer og repræsentationsopgaver i forhold til de østtyske selskaber, kontorer og diplomatiske arrangementer herhjemme. Ud over hæder og ære – eller den kommunistiske anerkendelse, der givetvis betød mest – blev arbejdet også belønnet med særbehandling i DDR, ligesom han blev honoreret med mindre beløb for artikler til østtyske aviser og tidsskrifter. Pengene blev indbetalt på en særlig konto i Østberlin og kunne bruges, når Carl og Leni rejste i landet. De rejser og besøg, som han selv og Leni foretog, f.eks. til kurstederne i Bad Brambach og Bad Elster, blev typisk også betalt af værterne. Et andet eksempel på, at man i DDR forsøgte at imødekomme hans ønsker, illustreres af datterens oplevelser. Hun var en af de få, der med Knud Jespersens hjælp fik mulighed for et længere praktikophold som socialpædagog. Hun rejste i det hele taget så meget i Østeuropa, at det blev for meget for den ledende Demos-aktivist Erik Jensen, der vredt udbrød: »Dig, mand, du bruger jo kun det parti som rejsebureau«. Men dermed fik hun også et mere usminket indblik i, hvad der gemte sig bag facaden.
