The stains are in the image area, and they can be seen to emerge while the paper floats in the developing bath.
When I move the paper from the enlarger into the developing tray, I hold it directly in my fingers (no gloves or tongs) near the edges. Normally I place the paper face-up into the developer (placing it face down was just to see if it would make any difference, which it hasn't). I agitate by raising the corner or sides of the tray so that the paper doesn't stay motionless but slowly floats around the tray. The stains, if they indeed form, can already be seen at this stage, as areas where the image does not emerge as strongly as in the rest of the photo. After the prescribed developing time, I lift the paper from the tray using tongs, hold it above the tray for a few seconds to let the developer flow off, and then place it into the stop bath. In the stop bath I use my hands to move the paper around until the image surface stops being slippery, then place it into the fixer tray, which I agitate similarily as the developer. After the prescribed fixing time, I take the paper out using a different pair of tongs, and place it into the sink to wash.
95% of the time, I use Fomaspeed papers, of different types (single and variable contrast), sizes and surfaces (velvet, glossy). Using paper from a single package, sometimes the stains form, sometimes they don't. I can't recall for sure if I've had this problem with Ilford MG Express which I've used on a few occassions.
While I cannot completely rule out the possibility of some fixer residue on my fingers (I will pay more attention to this in the future), I have not noticed that the stains would coincide with the places where I touched the paper.