Раздельные рабочие столы

Собственный набор иконок чего?

А про меню приложений, склоняюсь к тому, что FVWM можно научить

в кедах есть "activities", попробуй

> Есть ли такой WM в котором каждый виртуальный рабочий стол имеет свой собственный набор иконок и в идеале собственное меню приложений?

Нормальный wm управляет окнами, а не отрисовывает рабочий стол с иконками. Это делает отдельная программа (nautilus, rox-filer, pcmanfm и т.п. говнищще).

sawfish можно научить, по аналогии с разными картинками на разных воркспэйсах . Вешать на 'enter-workspace-hook свой хук, в нем дергать ту прогу, что отвечает за рабочий стол.

FVWM так можно настроить. Курите маны.

В ОС Emacs есть такой WM. windows.el называется.