Default settings of MySQL are in no way good to work with large databases.
Example: Virtual XEN machine, 512M RAM, default cache settings, database of 3.5GB. Queries taking 10 to 120 seconds, depending on the amount of joins/records returned.
Same database, other machine with 8GB RAM, caching is set to 512M for query caches, query_cache_limit 2G, sort, join, read buffers 256M, key_buffer at 2G, innodb_buffer_pool_size 4G, log file 1G, log_buffer 256M. Same queries 0.0011 sec to 2.5-3 sec tops..
You do the math. Lesson learned (maybe the wrong one): Indexing and proper database design is not everything. 🙂