Not the way to handle privacy ...

I was happy when I heard that 1.13 would allow you to hide your online status, but the implementation of this feature is terrible. What use is being able to hide your online status if people can see you are hiding it? Sometimes I want people to see I'm on, and sometimes I don't. But switching "view online status" to off is tantamount to letting people know I'm hiding.

The way it should have been done is that if someone hides their online status, they simply appear to be offline. Period.

The "not showing up in search at all" is a bug.