Existe un bug en Linux que aparentemente se da mucho al usar compiz, que hace que el segundo monitor de una configuración dual-head pierda los bordes (las decoraciones). En mi caso particular se da porque los monitores tienen distinta resolución.
Si estamos usando compiz y kde el responsable de dibujar las decoraciones es el kde-window-decorator.Si no estamos usando compiz, el responsable es kwin. El bug se da tanto con el kwin 3.5 como con el 4.0.

La mayoría de los workarounds que existen en la web son para compiz, yo adapte la solución para mi caso que es dual-head sin compiz y kde.

La solucion (transitoria) al problema es generar un archivo en ~/.kde/Autostart, en mi caso el archivo se llama kde-dual-head-bug:

$ cd ~/.kde/Autostart
$ vi kde-dual-head-bug
#!/bin/bash
kwin --replace &

$ chmod a+x kde-dual-head-bug

Lo que hace es volver a ejecutar el kwin, que en algún momento del arranque falla.