Não, claro que você tem que usar o Devilspie.
Algo como isso deve acontecer:
(if
(is (window_class) "Terminal")
(begin (undecorate) (maximize)))
Você pode até dar um passo além e maximizar todas as janelas usando esta regra:
(if
(is (window_property "_NET_WM_WINDOW_TYPE") "_NET_WM_WINDOW_TYPE_NORMAL")
(begin (undecorate) (maximize)))
Se você não quiser usar o Devilspie, poderá substituir o Metacity pelo Openbox, que suporta o recurso que você deseja.
Basta colocar
<applications>
<application class="Gnome-terminal">
<maximized>true</maximized>
<decor>no</decor>
</application>
<application class="Terminal">
<maximized>true</maximized>
<decor>no</decor>
</application>
</applications>
no meio do seu ~ / .config / openbox / rc.xml.
Ou você pode tentar wmctrl em vez de Devilspie.