Если это "теплый" старт, то поиск занимает, примерно, 1 минуту - из личного опыта эксплуатации в Москве (дома, провода, троллейбусы и т.п.). Я использую iPAQ 2210, HAiCOM 303, OziCE.

"Холодный" старт значительно дольше. Он бывает при первом включении GPS или если Вы включаете его удалившись на 120 и более км от места выключения, т.е. приемник выключили и увезли за 120 км.
Вы кстати зарядили в GPS встроенный АКБ?