sí, entendí desde tu segundo mensaje, lo que tienes que comprender es lo siguiente:
o pasas el estado del elemento dentro del mismo enlace, o bien pasas sólo el id, y donde recibes el id lees nuevamente el estado del elemento para ponerlo en un estado u otro.
Resumen: de la forma que lo estás haciendo ahora, cuando recibes los datos del id, no sabes realmente el estado del elemento.
la primer opción modificando el enlace es:
<a href="index_estado.php?id_dep=4">(cambiar)</a>
<a href="index_estado.php?id_dep=$id_dep
&dep_estado=$dep_estado">(cambiar)</a>
o bien, sigues pasando sólo el id, y en tu script donde lo recibes primero verificas el estado para después cambiarlo por otro.