I have set my KDE desktops up in a way that I'm very happy with. Instead of describing it to you, here is a screenshot:

http://theelectricuniverse.com/hostedimages/icons.png

Now, here's the problem. See the doomsday icon on the bottom right? Everytime I turn on my computer, it appears at the top directly below the "My Computer" icon. I know it sounds minor, but it really irratates me to have to move it every single time I start my computer, especially since I'm showing Linux to a large number of people, intent on converting them, and it's essential that there isn't the slightest thing wrong with my desktop when I do it.

I have "automatically line up icons" checked in Configure - Desktop.

I had a similar problem and i solve it by unchecking the "align to grid" option. On KDE 3.3 you can get there doing a right click on the desktop and then icons->align to grid.
Every time i want to align the icons i check this option and afterthat uncheck it again.

I hope this help.

I had/have that problem too. In Gentoo-KDE and Suse-KDE. What i have been doing is delete the icon on the desktop and logout of that session. Log back in and obviously it should be gone. Then recreate it and drop it where you want it. Log out and log back in again. It should stay put now. If it doesn't (which has happened to me ) i usually just hit something. That works too :-)

You can also specify the grid spacing:
I added this line to the ~/.kde/share/config/kdeglobals file....this line went below the
[DesktopIcons] section...so it ended up looking like this:

[DesktopIcons]
DesktopGridSpacing=25,0

with a bunch of other preferences under the same section....
After setting these values, I had to log out and re log in to have them take affect.
NOTE (If this doesn't work, you need to make sure that the "Restore Last Section" option is enabled.)

Heres what the values really do:

DesktopGridSpacing=x,y