The paper I've used is what was cheap at Fred Meyer (a local everything store when I lived in Seattle area): ProArt (made in Malaysia, company address at a PO Box in Beaverton, OR, a suburb of Portland), acid free, 140# (300 gsm) natural white cold pressed. It appears to be fiber reinforced (it doesn't wrinkle when wet) and came in a wire-bound book of 15 sheets, 7x10 inches. I've been getting as many as four 9x12 cm prints from a sheet.
My chemistry is the Formulary Traditional Cyanotype dry chemical kit; I haven't ever used the arrowroot starch sizing, but simply coat the paper directly. I have sometimes used one drop of the 2% potassium dichromate solution in 2 ml of mixed sensitizer, but mostly I get better results without it. And I haven't attempted a print in several months; since moving to North Carolina last fall, I haven't even opened the chemical bottles to see if the ferric ammonium citrate has gotten moldy.
It's very possible the ferricyanide in the first wash is acting like more ferri in the sensitizer, but it might also be reacting with unexposed sensitizer and causing or contributing to your bleeding. Seems to me there was a ferricyanide based "ink'" formula as one of the experiments in the chemistry set I had when I was in about 5th grade. I seem to recall that increasing the proportion of ferri in the original sensitizer would tend to make the print faster, which could cause fog you'd see as bleeding.