The urls you posted are correct. The only reason I can think of right now that you get a wrong theme would be an cache issue, be it browser or server. You can set specific album themes but those do not affect the search page. But maybe look if you set one somewhere accidentaly.
Do you use the html_Static_cache plugin? If so clear the cache and also that of your browser to see if that has any effect.
I never encountered this behavior myself and as far as I know we had no reports. It could also be your firewall affecting things (weird things happen often....).
Maybe my colleague has another idea later on.