Things fossilize because they absorb minerals, prettymuch turning whatever it is to stone. A twinkie could absorb minerals just like flesh could.
They'd have to absorb enough minerals BEFORE decomposing, to become a fossil.