Your informants are partially right. If you use bold, italic or bold italic in a font which doesn't have a properly linked set of relations, you will get back plain version type. Spacing may or may not rewrap.
I have often used the underline feature, however, and more than a few times used the outline feature. I rarely use the shadow style, because I get more control duplicating the headline, offsetting it a few points, and sending it behind the text box (background:none). That lets me control the size of the offset and color of the shadow.
I don't believe any of these substitutions has triggered a Courier substitution, however; as I mentioned, I usually get a "plain" style back. If your service bureau gets Courier, you might want to try a second service bureau with more sophisticated type handling capabilities.