Pues busca bién que algo haces mal.
Yo acabo de crear un form con borderstyle=0 y ShowinTaskBar=true, con un boton con el código que tu dás: me.windowstate=1, y cada vez que lo pincho se encoje y cuando pincho en la barra de tareas vuelve a aparecer, tantas veces como lo haga, de modo que algo haces mal o tu windows está configurado para reaccionar así.
He probado añadiendo: me.windowstate=2 en el Form_Load para comenzar maximizado y el resultado es el mismo, encoje al pinchar el boton y aparece cuando le pincho en la barra de tareas.
Igual tienes gremlins...
Suerte.
PD: Si no das con el fallo, intenta usar el programa en otros equipos, si no lo has hecho ya, a ver si es cosa de tu sistema operativo.