I also had problems with the search bringing back my visitors to the default site language. To solve it, in the admin panel, i went to :
Settings > Languages > Advanced Settings (click show)
and under URL modification code, selected the option :
Use Pre-Path Mode (Default, puts /en/ in front of URL)
This way, all urls add the language slug right after the root url, and i can use <?php bloginfo('url'); ?>
with anything i want after it in all my templates and the language always follows from one page to the other.
It also works with the default WP search.
Hope this helps!