I think the opinions here a little bit too damning on the prospect. One way you could figure out an Orthodox Prussia is to have the Kievan Rus expand farther into Baltic territory. Not impossible, since the Lithuanians were subjugated and forced to pay tribute in the 11th century and then later Polotsk expanded deep along the Daugava River. Some more successes in keeping the Eastern Baltic region in line and reaching closer to Prussian territory, so that someone unifying Prussia, be it the Sambians or one of the other statelets, could adopt Orthodoxy.
Prussia also had contacts with the Orthodox Rus. Novgorod, Kiev and Prussia maintained trade relations and there was a Prussian trade colony in Novgorod in the late 12th century. Not impossible that some of those trade routes could have brought the Orthodox religion if there was more incentive for it.
Not sure on keeping the pagan customs though. The Orthodox don't have a better track records of keeping pagan faith customs after Christianization (how much pagan folklore has survived in modern day Russia, again? Not sure if it's considerably more than Polish or Lithuanian respective pagan customs.).