Trace bitmap is probably as close as your gonna get. When i do work for some smaller companies I cannot belive how many of them send me low res crappy bitmap/jpeg images of their logos, I ask for eps and ai files but they dont have them.
What I end up having to do is to recreate the logo as a vector file. I am more comfortable using flash as oposed to illustrator, so what I usualy do is just import my image blow the jpeg up on one layer, make it a symbol and lower the opacity to about 80, and then I lock the layer and make a new one, and just use the line tool to very carefully draw out all the edges (of course zoomed in), I make all my line segments small and short so when you do zoom out the logo is is smooth, once done i delete the jpeg layer and fill in any sections with the appropriate colours, and delete the lines i drew. After that i select different parts of the image that could be smoother and just use the smooth option in flash.
However if you have illustrator or are good at using it Im sure the same type of thing can be done using paths and anchor points ( I havent had to use illustrator since last year so Im a little rusty)
Hope this helps, and i know what you mean how frustrating it is. Trace bitmap wont do it, its just gonna show pixels if you trace it too fine and if you dont trace it fine enough you will get rough edges. I find its only usefull if i need kind of a sloppy vector looking cartoony type image thats very simple.
Sorry about the double post. I made it in flash, but I then exported it to fireworks. When it gets to fire works it is in bitmap mode Kinda defeats the purpose. I saved it as a png file, which I thought was vector.
The best program to print it out is going to be illustrator, photoshop and fireworks are both raster.
I suggest to things:
Download the illustrator demo from adobes site (hopefully the demo prints, check that before you download it)
You can open the ai or eps in there, scale it with the scale tool or manualy entering the dimensions, and then print.
Other option is to see if theres a demo for Quark Express 5. Im 99 % sure it can handle vector files and you can just make a picture box, select the box with the hand tool, go to file > get picture and then size your image right on the page and print.
I would suggest illustrator just because if you run into any probs I be more helpfull with that.