> デスクトップのアイコンの情報がどこに保存されているか
デスクトップ、およびフォルダーウィンドウ関連の情報は、
　HKEY_CURRENT_USER\Software\Microsoft\Windows\ShellNoRoam\Bags\{数字}
だったかと思います。Vista や 7 でも同じかどうかは分かりませんが。


> アイコンを移動させる話ではないように思いました。 
というよりも、デスクトップの実態が ListView である、という話かと思います。
ListView であることさえ分かれば、アイコン位置の取得/設定は
LVM_GETITEMPOSITION / LVM_SETITEMPOSITION32 あたりで行えますね。

Vista や 7 では試していませんが、少なくとも 2000 や XP では

Private Declare Auto Function FindWindowEx Lib "USER32" (ByVal parent As IntPtr, ByVal child As IntPtr, ByVal className As String, ByVal windowName As String) As IntPtr

  Dim hwnd = FindWindowEx(FindWindowEx(FindWindowEx( _

      IntPtr.Zero, IntPtr.Zero, "Progman", Nothing), _

      IntPtr.Zero, "SHELLDLL_defVIEW", Nothing), _

      IntPtr.Zero, "SysListView32", Nothing)

という感じで、ListView のハンドルを得られます。
しるふぃんさんが紹介されたサイトでも、同様の事が記載されていますね。


# アイコン位置の“取得”だけなら、MSAAv2 で行えるのですけれどね…。

Imports Accessibility

Public Class Form1

    Private Declare Function AccessibleObjectFromWindow Lib "oleacc" ( _

            ByVal hwnd As IntPtr, ByVal objectID As Integer, _

            ByRef riid As Guid, ByRef ppvObject As IAccessible) As Integer



    Private Sub Button1_Click(ByVal sender As Object, ByVal e As EventArgs) Handles Button1.Click

        ListBox1.BeginUpdate()

        ListBox1.Items.Clear()



        Dim hwnd As IntPtr = デスクトップのListViewハンドル



        Dim accDesktop As Accessibility.IAccessible = Nothing

        Dim IID_IAccessible As New Guid("618736E0-3C3D-11CF-810C-00AA00389B71")

        AccessibleObjectFromWindow(hwnd, &HFFFFFFFCI, IID_IAccessible, accDesktop)



        Dim child = accDesktop.accNavigate(AccessibleNavigation.FirstChild, 0)

        Do Until child Is Nothing

            Dim L, T, W, H As Integer

            accDesktop.accLocation(L, T, W, H, child)

            ListBox1.Items.Add(String.Format("({0}, {1}), {2}x{3} => {4}", _

                        L, T, W, H, accDesktop.accName(child)))

            child = accDesktop.accNavigate(AccessibleNavigation.Next, child)

        Loop

        ListBox1.EndUpdate()

    End Sub

End Class