Hi Mazen,
Man, do I know your frustration!
I love to use transparency, especially when I'm doing more graphic-arts like stuff with Visio. I have a cheap HP laser printer,--it is a color printer and I'm proud of it--but it doesn't handle the transparency very well.
The solution I came up with was driven by the need to take drawings to service bureaus like Kinko's and get them printed out. These places usually don't have Visio installed, so you need a more universal format.
So, as you've done, I started with PDF, but that doesn't always get the transparency right. So I thought; "As long as I'm exporting, why not just do a high-resolution bitmap?"
And that is what works best for me. If your target printer is 600dpi, then export a bitmap at 600dpi. Your file will be HUGE, but you just need to print it, then delete it. Bmps also zip well, if you want to keep them around.
If you're worried about file size, then .jpgs or .pngs or .gifs might work well enough, although they tend to compress things, which might make your colors and filled swaths turn out garbly.
I've heard that the .tif format is intelligent and full of useful information, but I can't tell you exactly what that info is, and whether or not it will help with the transparency problem.
Good luck!
- Chris
[edit: Paul was faster!]