On pg. 64 of collected visions. These look like vostroyans. Would vostroyans make a good pre-heresy imperial army? Or should they be avoided because the fluff says they did not participate in the crusades.

i would say the artwork just represents one style of unit they had the imperial army is a huge thing and it has thousands of different regiments and looks as far as pre heresey goes i would think anything goes in imperial foot slogers

they do have cadians, elysians and catachan, and changed the name of the homeworld they come from, so yea go for it...

This might be handy - lists the canonical Imperial Army regiments. I believe the regiment you are referring to is the Urslavic 12th Infantry.

Vostroya was around pre-Heresy - it pledged allegence to Mars during the realm of strife and is close to being a Forgeworld (in 40K it has loyalties both to Mars and to the Imperium itself, with a government that is a cross between that of a Forgeworld and a more traditional Imperial system). The 'Firstborn' regiments themselves did not exist pre-heresy - they were formed as a form of penance for Vostroya refusing to send regiments to fight for the Emperor during the Heresy as they were reserving their population to work in the factories. However, the world will almost certainly have had troops during the pre-Heresy period - whether they would have taken the form of Tech-Guard regiments loyal to Mars or Imperial Army regiments loyal to Terra is unclear.