We've seen some very unpredictable results when changing autodiscovery rules. Steps to reproduce:
1. Create Rule A - Checks: system.hostname (always returns true/result)
2. Create Action - Discovery Rule A = link to template A
3. Let Rule A discover Host A, Host B.
4. Change Rule A - Check: system.uptime
5. Change Action - system.uptime greater than 3600 seconds = link to template A (only Host A should meet this criteria), unlink Template A from Host B at this time.
6. Even though the new discovery rule should NOT cause Host B to link to template A, the next scan will do so.
To get out of this non-consistent state we've had to truncate the dhosts/dservices tables in the MySQL database and restart the zabbix server (clear the discovery process memory.)