This has actually been my experience with Magento itself. It's a huge piece of software that is not known for being efficient or fast. At a web design shop where I used to work, we installed it for a few clients of ours. We were hosting everyone on our own monster dedicated server, so there were no noticeable issues at first. As one of the client's product catalog grew larger and larger (into the thousands of products), traffic spikes and certain operations (especially searching) would slow the whole server down in a very noticeable way and affect everyone. Looking at the server logs, there were times where Magento would run over 100 queries for a single page, run of out allocated php memory, or exceed script execution time.
We ended up having to purchase a new dedicated server just to move our 4 or 5 Magento customers to so other customers would stop complaining that their website was slow and so that we could bump up the connections, queries and memory limits. This got a little better with successive releases, but it was always a pain to upgrade because so many templates would change.
The only way I have seen Magento get faster is with faster/better hardware and dedicated servers or high end VPS boxes for each installation.