Thank you very much sharing your experiences, lately people have been so negative on the forums it's easy to forget the silent masses who have little or no trouble with WordPress.
You're right that that "Search:" should be attached to the form element somehow, and
<label> is the correct way to do this. I have added this to my todo list for 1.1. Thanks for pointing that out.