it must search through every single unspent output for every single address in the wallet. Since there are thousands of addresses and thousands of unspent outputs for each address, it can take a long time to search through everything in order to create your transaction.
Does really wallet.dat has no indexes for unspent outputs?
Well known that in Relational-DB we can find 1 record from 1 million records less than for 1 second using indexes.