This is normally due to a restored configuration backup - one that overwrites your 'safe-mode' settings. The person you spoke with at your host may not know about this. The other issue may be you have a virus or have been hacked. As you know 'safe mode' is a security threat nowadays so I'd be wary that someone did not hack your sites and is planning or is using safe mode as tool.
Can your host tell you what IPs have connected to the admin and server; furthermore, can they check if any SSH activity is showing in their firewall/security set-up, with specific emphasis on your sites?