My desktop shortcuts stay where they are put with Vista; there's probably some kind of auto-arrange option that you've left enabled (XP used to have a "periodically clean my desktop" option that was annoying until deactivated)
One thing you may be doing that I've noticed with some versions of windows: if you navigate to your 'desktop' folder using Windows Explorer, and do ANYTHING with that view, it sometimes messes up the desktop itself. I've seen that with Win 2000. I try to avoid touching the desktop folder nowadays, so not sure if it afflicts Vista or not.