The time taken for metadata is dependant on many things as I understand it. How many and which plugins are installed/enabled. How sources are configured. Internet speed, the load on the metadata source and your connection.
I have canceled metadata downloads because they were taking forever and tried again a few minutes later and the result was almost instantaneous. I am sure that the same search was performed in both cases, so it is often outside of calibre's control.
Post by kiwidude in this thread explains things a bit.
I prefer to exercise a bit of patience and use the calibre metadata download then any other method I have come across, It has been very helpful with my many, many ebooks, but I can understand your frustration.