1826
I would change host. Many ISPs enable safe-mode as a knee-jerk reaction after a hacking attempt. We use three hosts, two with safe-mode ON and one (our XOOPS host) with safe-mode OFF. Out of the three, it was one of the hosts with safe-mode ON that had their server hacked in September. PHP safe mode played no part in the attack at all. It is by no means 'essential' for security.
I have no doubt that the small print in your service agreement enables your host to do exactly as they please. However, they have changed their terms or service in mid-stream, which has a direct impact on your ability to continue using them as a supplier. I would change host and demand a refund for the portion of the year for which you were unable to use their service. Whether you succeed in getting a refund is another matter!
If you do shop around, be sure to check any prospective host's PHP info file (normally called phpinfo.php) to see exactly what they offer. If their website doesn't have a link to a PHP info file, I would be very careful. Many hosts offer cheap PHP/MySQL hosting, but the service is often severely restricted. Safe mode may be on, you may not be able to use gd-lib, PHP upload may be disabled. One member of this community was offered free hosting and unlimited bandwidth - but the host automatically changes folder permissions from 777 back to 775, due to what they call 'security' issues.
If your host 'hosts' your domain name too, check that they do not charge an extortionate amount of money to transfer domains away from themselves to another registrar. As competition has increased, hiking-up domain-transfer fees has become common practice in order to make leaving prohibitively expensive. Check their TOS every year and keep screen-shots or a printed copy.