Put new phrases on the signs that will make people less likely to want to steal them. "Out of Order" is a culturally engrained; a simpler, less desirable phrase might produce better results.
Remember, consider the motivation of people stealing these signs. Stealing signs is an act of rebellion and fun for many thieves; "Out of Order" signs will go above their toilets or on doors.
You might ask how I know this...well, I didn't grow up in DC, but let's just say I did more than my fair share of rebellious acts.