"No matches found" for recently added tracks

[squid]

Hi there, the search feature is great but I have recently added about a dozen new albums and none of them can be searched, I consistentlly get "No matches found". I tried keywords from the artist, album and several songs but nothing on these albums can be found. The albums appear in the library in the left panel, as well as in "Recently added". I can also play them just fine via Subsonic. They are the same format as the majority of my library (flac).

I tried "Update search index now" several times, no errors are logged, but still I cannot search for these albums.

I'm using 4.6 (build 2583) – December 6, 2011

There are roughly 80000 tracks in the collection.

Regards,
Robert