I would assume the speed is dependent on how well indexed the database is and how common or unusual the DVD title is... My system picked up "The Adventures of Tin Tin," for playback, very quickly... I don't know whether LinuxMCE saves a snapshot of the database or whether that's purely a function of it doing an internet search of the databases. Checking the Wiki might give you a clue as to that.
Personally, I usually rip the DVDs I buy to AVIs, and manually transfer them to the external HD that I use, ... saves space, but means I have to supply my own meta data.