If you can't get date ordering to work using:
http://www.domain.com/?s=searchterm&orderby=date&order=desc
try
http://www.domain.com/?s=searchterm&orderby=post_date&order=desc
i.e. use post_date instead of date. Tested this in TwentyEleven and Thematic - seems to fix it for me.
Hope this helps someone :)