I noticed that shoes with narrow toe boxes don't fit very well in my bindings and they slide out easily. Fatter shoes would probably work better.

Try leaning in more while you do a toeside turn.  If that still doesn't work for you try to get low, grab the outside of the board, and then lean in far to turn. 

I'm not the greatest though at doing sharp toeside turns, I sometimes catch an edge and then fly off of my board.