The search button was being specifically removed when the back button was shown - I'm not sure if there are gnome style guides somewhere to say this is desired behaviour?
However, I removed the code doing this and this is how it looks..
The search button stays on the left - which is good in that the always available functionality isn't moving around the UI, and the transitional one (the back button) appears next to it when needed.