OK so I have been using Vista for some time now and really getting to like its little features, one of them being I can log on as a regular domain user with no admin rights on the Laptop and when ever i need to install something it prompts me for credentials.
So any way I was installing another laptop with Vista on it for one of our Application Developers and I was wanting to put a shortcut on the all users desktop. So I went to C:\Users (as that is where the profiles are kept these days no longer C:\Documents and Settings) and went into all users.... but there was no desktop folder 
. Where could it be I asked myself.
I noticed that there was a folder called "public" in the Users folder so I just thought hang on its been a great Microsoft renaming thing! and low and behold there was the Public Desktop folder. However it was showing up as Hidden.
So there you go the "All Users" Desktop is located in:
C:\Users\Public\Desktop
However it is shown in the explorer window as Public Desktop but if you do a start run and type in the path above it will take you there.
