Are you using the ini token lazyLoadIcons=True? This was added in LabVIEW 2011 f2 and later to fix an issue described in the this KnowledgeBase. If you do have that token enabled you will need to turn it off and rebuild or add additional tokens as described in the KB.
If you aren't using this then working with the AE to reproduce the problem will be most beneficial. The icons are saved within the VI files themselves so this shouldn't have anything to do with the RTE. If the icons are showing up in the exe on machine I wouldn't expect them to show up on any machine.
Regards,
Jon S.
National Instruments
LabVIEW NXG Product Owner