Database Performance Degrading (again)

We have an application with a SQL Server 2000 back end that is fairly
database intensive -- lots of fairly frequent queries, inserts, updates
-- the gamut. The application does not make use of performance hogs
like cursors, but I know there are lots of ways the application could
be made more efficient database-wise. The server code is running VB6
of all things, using COM+ database interfaces. There are some
clustered and non-clustered indexes defined, but I'm pretty sure
there's room for improvement there as well.

Some tables have grown into the millions of records in recent months,
and performance of the application slowed to a crawl. Optimizing the
database helped a little, but not much. We know that several million
records in a table is a lot, but one would think that SQL Server should
be able to still handle that pretty well. We do have plans to archive
a lot of old data, but in the meantime, we were hurting for a quick
fix.

So we threw hardware at the problem, and transferred the database to a
new, more powerful server. The performance improvement was dramatic.
Transactions were many many times faster than before. Without
implementing any of the other more difficult performance improvements
we have planned, we suddenly became minor heros. :-)

Well, the honeymoon seems to be somewhat over. While performance is
still much better than when the database resided on our old server,
performance appears to have degraded rather significantly again.
Performance is also not significantly better with fewer users on our
system. What the heck?

Yes, the database continues to grow unchecked as we haven't quite got
an archive utility in place yet, but the growth is relatively gradual,
so you wouldn't think that would be the issue. The database is
optimized on a weekly basis, and our web and database servers are both
rebooted monthly. Our database administrators don't seem to have
answers, so I appeal to the experts reading this forum to maybe offer
some clues.

Prior to posting I did do a fair amount of research to see what people
have suggested in similar situations, and ran this by our database
admin. Here's what I can tell you from this research:

- Statistics are updated weekly along with whatever else the database
optimization does

- We do not use the "autoshrink" option for automatically shrinking log
files

- Regarding preallocating space and setting growth factors for log and
data files to minimize time spent allocating disk space, our admin
says, "We do allow database files to grow unchecked, but we do monitor
growth and manually expand as needed. Autogrow is typically set in
50MB increments or less as the amount of time it takes to expand this
amount is negligible."

- Transaction logging is turned on, and data and log devices are on
separate physical disks

- The database server is monitored to ensure no process is hogging all
of the CPU, I/O or memory