I just noticed that my Google search history is missing in the browsing
history (IE. However if I use the search box of the browser (I have
configured Google as the default search engine), the search history is
recorded. This behaviour must be recent, it has worked correctly before,
also with IE8 I guess.

After some searching on the web, I thought it might have something to do
with InPrivate browsing. However, turning this feature off (running
gpedit.msc) did not solve the problem. Does anyone know what's wrong?