The easy solution is probably in Illustrator. I don't use Illustrator much, but Illustrator has an option wherein all font data is removed and replaced with vector outlines of the fonts, rather than actual font files. Designers have to do this before sending brochures and such printers because you can get the exact same problems as files move from one computer to another. I think your best bet is to save your Illustrator files in a way that is not font dependent.

If it's a simple header / footer type letterhead, you could just export your design as a maximum quality jpg (one for the header and one for the footer). That will rasterize rather than vectorize your data, but it still removes the fonts.

Thanks for the reply! I've just started to really figure out Illustrator myself, so that info will be most valuable in the future.

As for my current problem, I just transferred the image file to an office PC running Word 2003 and the font issue was fixed. But I am going to try your Illustrator tip so that I can ensure cross-compatibility.

Thanks again!