It is a well known issue in Media centre, which in my opinion, is the only thing that has not been fixed from xp through Vista to 7mc. Have a look at the link below, there are various suggestions on fixing it - one that has worked for me is to boot up the box, load mce & then go into music & let the library load completely before touching anything within it. My own library contains 1200 or so albums & loads within 2 minutes, but i still think it should be instantly available.
Search - The Green Button