Let's do a little thread clear-up because it's getting a bit confusing.
If you have the source then a bitmap's or vector's will scale down.
Not sure where bitmap's come into it, any sort of image can scale both ways but the quality of a raster will always diminish, more so on scaling up. The artefacting on downsizing is rare. We'd need to see the logo to work out why it might be doing it. A vector is what you want.
I have created the logo in Photoshop.
Excellent, is it just text or does it have some geometry too? If the text is still editable then it's vector based. For the geometry you want to be using the pen tool.
most likely you would be better off making it a vector format in illustrator, depends just how simple or complex the logo is really.
Lots of sites are using .svg formats for logos, that require the ability to scale.
Illustrator is a lot nicer for editing vectors, but not critical. PS will do the job too if you know how. SVG is useful on the web as you say, but his requirements are for an A3 print and an email signature so I'd suggest an EPS and a PNG.
Ideally you need the logo in eps format. This is a scalable format. I don't think photoshop does this. As Pariah says Adobe Illustrator will do this
There are a lot of containers for vector paths, PSD, EPS, AI, PDF, SVG.
To really help you further OldCoals we'd need to see the logo.
