We at one stage had to import 56k records. WITH VALIDATION was vital and there were a lot of rules firing. it took a Week to import on a 2.5GHz and 2GB ram. (That was ver 3.0 and there have been a lot of improvements to the built in functions since then, and rules have gotten simpler and less intesive, but it still takes a relatively long time to import)
We tried various ways to improve importing, and tested on various machines, but ended up settling on a planned import schedule as part of our deployment, where we broke up the import into separate batches and imported them according to the schedule.
It is just vital to plan ahead for DB build time when you are rolling out your application for your clients.