When rebooting a monitored server, zabbix server marks it as unavailable, and the status isn't changed when the machine comes back online.
The only way to restore correct status (monitoring keeps working ok for other items) is to stop zabbix_agentd for a period longer than the item check time (5 minutes).
Since status is a check perfromed only on the server, I guess the problem is there.