I was going to recommend .gif or .png, until I realized you had tried that. I’m not sure why .gif and .png don’t work, because they do for me. Are you sure transparency exists in the original .gif / .png files themselves? Not sure about other versions, but in Word ‘07, you may also use the format picture tools and set a transparent color (note that it will take out that color everywhere in the logo).