EDIT I thought I figured it out, but I tested with DuckDuckGo and it does not redirect you to a different domain. Yet the problem still occurs on that site. So the mystery continues. The first workaround might still work for you if you are using Google. The second workaround should work in any case.
I am able to reproduce this bug and have a few workarounds.
The reason this bug hasn't been fixed yet might be that it not always occurs when in full screen, you have to be in a different country than the U.S.A. too. It seems that the redirection to a different country domain causes this behaviour. I assume all the Safari developers reside in the U.S.A., so they never experience this behaviour.
Now for the workarounds:
Option 1
If you are using Google, visit google.com/ncr. This sets a cookie preventing redirection to a local Google site. The bug will disappear until you clear your cookies. There should be similar options for other search engines.
If you want it to disappear permanently or if you want to keep using your local site, we have:
Option 2
Add the AnySearch extension to Safari and configure it to use your search engine of choice. The bug does not seem to occur when using this extension.
I filed a detailed bug report with Apple btw. Hope it gets fixed in the near future.