ano, složitost je klasicky O(n), takže pro kód, kde záleží na rychlosti (mail klient, web browser) to není. Pro malá data jsou však ok, i když mi plisty připadnou čitelnější .-) Blíže viz například https://www.emacswiki.org/emacs/AlistVsPlist
Důvod je jednak historický (hash tabulky nebyly, a v prvních lispech byly v property listech vázaných k symbolům i hodnota nebo funkce k symbolu), jednak pořád praktický - interpretace volání funkcí s key parametry ve stylu (copy :from X :to Y :start 10) přirozeně vedou k plistům. Ke krátkým plistům, a u nich není asymptotická složitost až tak relevantní (ostatně, podívejte se jak běžný command line program parsuje své parametry).