The wackiest outcome I could imagine would be a post-USSR confederation forming out of Poland, East Germany, the Czechs, and Slovakia. And given that the easiest way to do that is to have the USSR fall harder and faster (outright civil war?), Kaliningrad would likely be lobbed off and become the fifth member of the confederation.
The Confederation would clearly be Polish-dominated, but with enough independence for the member states that it doesn't feel that way. Thus the GDR survives as political entity, though de jure not entirely sovereign (as opposed to simple de facto).
And the only thing I can see tying that motley crew together into a Confederation would be if the Eastern European leadership were on the
leftist side of a Soviet civil war. Otherwise nationalism and the option of more direct unilateral ties to Western nations would fragment them.
So--civil war in Russia; the more left-wing Communists lose--either to more rightist Communists of a more Stalinist mold, or to anti-Communist nationalists. But somehow, the Eastern Bloc leadership manages to hold on and recognizes a need to band together to stay afloat.
Now it is a fact OTL that not all opposition to the Soviet-controlled Eastern system came from the Right; other dissidents included more idealistic Communists who wanted to see the system reformed, either within their own country or for the bloc as a whole.
So perhaps it goes like this:
1) A reformist movement in the Soviet bloc as a whole gains favor and has some success, both on economic fronts and on the front of general political culture, winning over more genuine and broader legitimacy for the Eastern Bloc governments.
2) Unfortunately the success is mixed; especially in the USSR there are both bottlenecks and conflicts of interest; a somewhat Stalinist backlash takes form and when the reformist leadership stumbles, in Russia itself there is a nasty power struggle, escalating in some places to a shooting civil war (but not one that goes nuclear, as it just might in a split Soviet Union!)
3) However, in the Eastern bloc nations, at least in the ones simonbp mentioned, the Stalinist side, which is prevailing in Russia, has no traction; defeated reformist Soviets flee to the European capitals and help dislodge what forces and agencies the rightists have there; the rightists gaining control in Moscow and eventually throughout the Soviet Union itself (perhaps having lost Kaliningrad--and hey, what if they lose their grip on Leningrad too!) recognize that they had best cut their losses and concentrate on negotiating a settlement with the new Central Bloc, involving verifiable agreements on limiting arms and otherwise preventing the Central Bloc from becoming a Western staging area for an attack on the remaining USSR.
4) The new Central coalition is prevented from simply joining the West as a bunch of independent nations by their shared reformist/leftist version of Leninism, which is economically successful enough to pre-empt any powerful organized sentiments for ditching the Marxist regimes completely. With success comes a certain openness in internal politics, enough that the various national regimes enjoy legitimacy on their own hooks. They confederate both as a military alliance and to form an economic planning and cooperation bloc. They continue to trade with the USSR despite the bad blood of the recent Soviet civil war, but both sides haggle more firmly over terms.
This presupposes that they guys running the various former Warsaw Pact nations (BTW, they may well call the new federation a second Warsaw Pact!) were quite different people from the ones OTL of course.
In particular I'd think that events in Poland in the 1970s, that led up to
Solidarnosc and General Jarulzelski's coup, would have to have gone quite differently; perhaps the Marxist/socialist reformist elements that fed into the rise of Solidarity OTL instead gained traction in Poland and other East Bloc states and eventually Moscow as reforms of the official Soviet-ruled systems. Otherwise, if Poland moved as OTL to any degree, I'd see no chance whatsoever of the Poles retaining any Marxist government; they'd ditch it for a more right-wing one immediately and seek ties to the West at once.