304 and some other Austenitic S.S. grades can be "sensitiized" to corrosion by improper thermal treatment.  One of these improper treatments is to weld 304.  304L(low carbon) is less sensitive to sensitization by welding.  316, 321, 347 progressively better for welding.

What is the exact thermal history of your 304 raw stock?  Was it purchased to a specification?  If it was cooled too slowly from the cystallized temperature through the 1500F to 800F temperature range, it will be sensitzed.

If it has been sensitized, yes solution annealing will de-sensitize it which restores the corrosion resistance.  I think it will also demag it but don't recall.  There are a number of S.S. experts on this forum and one or more will shortly reply on the magnetic aspect.

Yes, SS castings are often slightly magnetic.  You need to determine why.  Is it residual delta ferrite (most likely) or some other secondary phases (very bad).  This could also be a surface condition.  You need to look at some sections and actually measure how manetic the material is.

The chemistry of your parts may be one factor.  Determine the composiotin and plat it on a modified Schiffler diagram.  This will tell you what the equalibruim ferrite level is.  With Ni being expensive your supplier may be shaving and giving you a higher FN.  This can be offset by increasing the Mn or N.

Annealing is usually helpful in improving corrosion resistance.  Heat to 1950F, hold for long enough for everything to get uniformly hot, and rapid cool.  If you do this in air you will need to pickle the parts to remove the oxide and Cr depleated layer.

You may want to try pickling some parts as is.  If the real problem is just in a surface layer this might remove it.

You also need to make sure that the passivation was the last operation.  There should be no machining or even handling (other than packing) after.

= = = = = = = = = = = = = = = = = = = =
Corrosion never sleeps, but it can be managed.
http://www.trenttube.com/Trent/tech_form.htm

Ferrite in stainless steel castings prevents liquation cracking. While the ferite content is normally less than 10%, I have often seen it greater and as high as 24% in 304 type castings. Corrosion resistance is adversely affected with high ferrite contents.  It is adviseable to limit ferrite content in your purchase specifications for stainless steel castings.

One can also add that the ferrite content will rise when the casting has thicker sections (slower cooling). The Leger-diagram is a modified Schoefer diagram, which in turn is a modification of the schaeffler-diagram (to include N in the Nieq) gives an estimate of the ferrite number in relation to the composition and the section thickness. (M.T. Leger, ASTM STP 756, 1982).

Another fact to consider is that handling of the casting(s) may induce iron contamination of the stainless surface. This can occur during descaling if steel or cast iron grid is used and if this is not followed by a proper blasting with an iron-free non-metallic grid. Another source of contamination can be the steel or iron dust that's all over the place in foundries. This can be examined by a ferroxyl test.

Your description of the red rust on the surface points to my opinion more in this last direction.