Yes, calibre does slow down more as more books are added. (before I go on, let me just say that I absolutely love the program and I very much appreciate all of the hard work that all of the developers have put into it. I can't tell you how much I've wanted something like this forever. It's just awesome).
I have a collection of approx 2,500 books in calibre (which is less than 10% of my whole collection) and it takes about 2-3 minutes to load. The SQL database has been checked for integrity, and on and on. It's just slow to start. I have a 3 GHz quad core PC with 8 GB of ram. I do very cpu/ram intensive design work regulary. The problem is that I have close to 30k ebooks and I'm hesitant to keep adding them to calibre because of the performance tax. So, while I agree with another poster's comment that robustness is preferrable to intial load time, there are ways to improve database speed. Take XBMC for instance (not really a fair comparison since it's been around quite a bit longer than calibre, and has a fairly large dev community). I have close to 4,000 movies in my XBMC database yet the program takes less than 3 seconds to startup. I saw the comment from a developer earlier about how there was no "silver bullet" for improving load times. I'm just curious then, why do programs like XBMC load so fast comparitively? Believe me, I'm not pointing out flaws with calibre. Quite the contrary, I have no bones to pick... I just find this an interesting discussion.
By the way, I'm a software designer... is there anything I can do to help the project?