Codice PHP:
<?php
$lnk 
$_GET['css'];
if(isset(
$lnk) && $lnk == 'change')
{
    
$prop 'red';
}else{
    
$prop 'blue';
}
?>
<div style=" border:2px solid <?php echo $prop?> ">

sono il div che cambia</p></div>
[url="prova.php?css=change"]cambia colore[/url]

[url="prova.php"]ripristina[/url]
testato e funzionante, lo devi solo modificare a seconda delle tue esigenze.
Cmq non capisco perchè con js non ti vada bene.
Con questa soluzione ti si presenta il problema dell'url rewrite!!!