Dear Shane,
As you may have an explicit rule for host removal, the Zabbix server needs to calculate the time passed since last host online 'event' to current time. Since you have not defined a rule for host removal, Zabbix server may consider them temporary offline. You may refer to this topic via link in manual: Host Discovery The tables mentioned are for that, an entries will be deleted from them ASAP the removal rule will take place on its condition. The host autoremoval (purge) is documented only for removal hosts that are not a part of discovery network.
Are there any conditions I can add to a discovery rule to only act on hosts that are online by a discovery check? I don't fully understand the Up, Discovered criteria and how they relate to the state of the hosts or discoverability.
So, if the host fulfills a "Discovery check" user-defined rule, it has a state of "Discovered" and "Up". So (lets say we're discovering hosts, not services, with fping/ping build-in utility), the following events will take place:
- Host discovered - mostly first discovery
- Host up - several successful discovery tests
A further scenario depends on your settings in "Update interval" and actions for discovered hosts. Let's say you did not discovered your host in 5 checks, each takes place in 10 minutes. Then you'll have 5 "Host lost" or "Host down" (All services of a host are 'down', consecutively) events, that can lead to one way of behavior (probably to notification). If there are any other event type for host/services, you may want to modify your actions as needed.
May be you got confused by 'discovery' and 'up/down' event terminology, so discovery - is a process, in which we iterate through all specified hosts and try to figure out their availability, while up/down - is an event, in which we judge what had happened to a host and what can be its status. You may substitute host to service, the aim is the same.
What I recommend you is to pay an extra attention to discovery rules you may have and try to define a host removal rule, which, I think, may help you. Please refer to manual link I enclosed above.
Another instance repeated today;
IP: 192.168.10.36. Deleted this host from Zabbix
Zabbix shows it has not been detected using any checks in 4 months;
Yet it is still being added to Zabbix with appropriate actions;

The host definitely does not exist and does not respond to SNMP or ICMP;