I had a look at AnkhSVN (great add-in by the way), and I found what I was
looking for.
As I feared, the process of manipulating icons in the Solution Explorer
treeview is not straight forward.

The way AnkhSVN solves the case is roughly like this:

- Obtain the solution explorer window name, from the EnvDTE.Window reference
of the window
- Get an IntPTR reference to the main window
- Search for the solution explorer (location depends on how it is docked)
   - Use FindWindowEx() from Win32 COM and traverse all main window childs
and floating windows until it is found (using the solution explorer window
name)
- When it is found, locate its UIHierarchy child window by name
("VsUIHierarchyBaseWin")
- And then finally locate the treeview window ("SysTreeView32") which is a
child of UIHierarchy

- Once you have a handle to the tree view, you may use Win32 COM method
calls such as SendMessage(), in order to set its image list
(TVM_SETIMAGELIST) and traverse the tree view (TVM_GETNEXTITEM).

What we want to do in order to change icons of the solution explorer items,
is replace the image list of the treeview with a self-drawn bitmap strip,
which can hold several icons in one bitmap.

Once the image list is set, we can set the icon for each item in the tree
view by traversing the tree view and using sending the message TVM_SETITEM
for each item.
AnkhSVN uses status icons and overlay icons in order to independently draw
two different statuses on a single item (such as "Modified" and
"Read-only").
We bake the overlay and base image indexes into a TVITEMEX struct, and pass
that as value to the message.

For a complete understanding you should consult the code of AnkhSVN.
Classes of interest are:

Ankh.Connect                                              (obviously)
Ankh.Solution.Explorer                                 (convenience methods
for the solution explorer)
Ankh.Solution.SolutionExplorerTreeNode     (abstraction of the solution
explorer nodes)
Ankh.UI.Win32TreeView                             (tree view abstraction)
Ankh.StatusImages                                       (tree view image
list enumeration)
Ankh.status_icons.bmp                                 (the icons)
Utils.Win32                                                  (Win32 COM
methods and constants exposed)

Hope this may help some guys out.. peace!

Best regards,
Andreas Larsen