Two theories: first layer expansion and overextrusion.

If it’s first layer expansion, what’s happening is that your nozzle is too close to the bed when printing the first layer (so, less than 0.2mm if you’re printing at 0.2mm layer height) causing a line of filament to “spread out” more than it should. Over long lines of filament like those on your first layer, that effect can compound. Ultimately it’s trying to put more plastic down between those outer layers than can fit, causing it to “ripple”/wrinkle up. The fix would be adjust your z-probe-offset to make sure your nozzle has just a little bit more space above the bed on the first layer and then autolevel. Or on a machine with no z-probe (with just a z-endstop), to manually level the bed but leave a little more room between the nozzle and bed. If you go too far, you’ll end up with first layer adhesion problems. Like, the first layer will curl up on the corners or will pop entirely off the bed mid-print.

If overextrusion, what’s happening is roughly the same as I explained above. More filament than will fit is being laid down between those outer layers, causing it to wrinkle. The fix is to turn down your extrusion rate.

I don’t think I’ve ever had issues with overextrusion myself. But I’m pretty familiar with that first-layer-expansion issue. And to be honest, when I have that issue, the wrinkling I have always happens parallel to the lines of filament on that first layer, while the wrinkles in your picture seem to go perpendicular. I still think those are the first things I’d try, though. So YMMV, but hopefully what I said above helps.

Also, I’d be skeptical that flotsam or scunge from previous prints could be the problem here specifically. Especially after soap and water didn’t solve it.

Anyway, my 2¢. Good luck! Definitely worth reporting back if you find a solution!