Well, it is probably that someone else is using your computer without you knowing it. You can read through Basic Troubleshooting, and see if the steps there will help you (possibly an extension is casing this).

It's definitely not someone else using it, as there's no-one else in my household. Like I said, the other strange thing is these 'mystery searches' disappear quite quickly from the history as well! PS: I'm going through the Basic Troubleshooting, just in case, and will feed back after that.

Found it! Went through all the Basic Troubleshooting tips and found that the last (of course) extension I checked was the cause: TrackMeNot - "it runs in Firefox as a low-priority background process that periodically issues randomized search-queries to popular search engines, e.g., AOL, Yahoo!, Google, and Bing. It hides users' actual search trails in a cloud of 'ghost' queries, significantly increasing the difficulty of aggregating such data into accurate or identifying user profiles." I had recently downloaded it, together with a few other privacy enhancing extensions like ghostery, in response to google's changed privacy policy, without realizing how it exactly works... Apologies for the fuss!