I have a similarly sized contact list and I've found that the Voice Dialer is both slow to load and slow to find responses on my Moto Droid (on 2.0, 2.1 and 2.2). I stopped using the Voice Dialer and started using Voice Search (aka. Voice Actions) by saying "Call Jane Smith mobile." I've found Voice Search to open quickly and to find contacts quickly. Both of those apps came preloaded on my phone and are from Google.
While I don't know the architecture of either app it would make sense to me that the Voice Dialer would be affected by the size of the Contact list more directly than the Voice Search app.