They do. Both LS and Acc will Lobotomise its ability and kill the Phoenix, BUT not on your turn. Your opponent can save it on his turn before attacking.
As such, you at least need two cards to instantly kill it like you would with any other creature. Since the Phoenix gets to attack when you use soft counters (because there are only soft counters) like LS, you still have to take its damage. That means most Phoenix counter strategies involve healing as well, furthering the notion that Phoenix gives card advantage.