Hands down, PDF is the best way to exchange graphics between programs if both programs support it. Unfortunately, Powerpoint does not natively support PDF. It uses a filter that converts PDF's to a bitmap (defeating all the advantages of the vector format), and its default settings yield the really poor images you are complaining about.
On a Mac, I create my presentations on Keynote, which handles PDF's natively. If I must for compatibility reasons, I export the Keynote to Powerpoint when I am done. The export filter in Keynote does a much better job of creating readable bitmaps for Powerpoint than Powerpoint itself does.
On a PC, your best bet is using the PNG format. Select the graphic, right click, Save As..., and select PNG as the file format (I've only used a Mac since upgrading to 7; your mileage may vary but I remember this working on a PC). It's a little blurry, but acceptable at the resolutions usually available on a projector.
I feel your pain. One does not always get to choose the medium one uses to communicate, but we do the best with what is imposed upon us.