Przeszukiwalność jest rzeczownikiem utworzonym od przymiotnika przeszukiwalny, a ten z kolei powstał od czasownika przeszukiwać. Można się domyślać, że przeszukiwalny to ‘taki, który da się przeszukiwać; taki, który można przeszukiwać’, podobnie jak np. reformowalny to ‘taki, który da się reformować’, zjadalny (pot.) ‘taki, który da się zjeść’, osiągalny ‘możliwy do osiągnięcia’ itd. Przeszukiwalność to zatem ‘cecha tego, co jest przeszukiwalne; możliwość bycia przeszukiwanym’.
Oba wyrazy (przeszukiwalność i przeszukiwalny) są poprawnie utworzone (jeśli mają podane tu znaczenie) i – jak można stwierdzić, przeszukując internet – są używane.