How many rows are in the result set? You may get the result set back on
the SQL Server very quickly, but if the bar charts are constructed using
tens of thousands of rows, they won't be generated until the entire
result set has been generated and processed. If SSRS is on the same
server as the database, then transporting the result set over the
network will not be an issue. If the MOSS-based site has to pull the
records over the network and then generate the charts, then you'll be
waiting for all the rows to traverse the network first.

The table that stored procedure pulls data from is large ... like
300,000 records. Though this is just a test environment, production is
expected to have around 10 million records in this table!

Also, sql server and SSRS are both installed on the same server as MOSS.
The machine itself is a virtual machine with 3 GB RAM. The host machine
is 3.0 Ghz dual xeon with 8 GB RAM. I think this should be ok for the
test environment with just 300,000 records which is definitely not huge.

Now, the result set actually returning from the stored procedure is not
huge either. Right now in test environment, result set has anywhere
between 10 to 100 records. The stored procedure itself is very fast as
its returning result set within 2 seconds from the query analyzer.

For large reports, SSRS has the ability to "schedule"
reports at certain times and then view the results of
this generated report.

Is this a feasible solution?

Ok, it sounds like you've eliminated SQL and network transport as the
issue.

The only other idea I have is the IIS worker process. If you generate
the same report twice in a row, does the second time run without delay?
If the delay is only on the first access, it may just be w3wp.exe waking
up...

Nope, the report takes the similar amount of time everytime it is
pulled, around 30 - 35 seconds after clicking on "generate report"
button.

Someone suggested me to look at the logs of SSRS by importing them in a
sql database and analyzing the bottleneck. It turned out that it's the
"Rendering Time" which is becoming the bottleneck. Interestingly it was
found to be uneven and we were not able to find a linear or even
exponential relationship between the rendering time and the row count.

All of this makes me wonder if SSRS is really an "enterprise level"
reporting tool or is it us missing something ? is there an article or
best practice for using SSRS? How can we optimize the rendering time?

That's a good question. Our implementation pulls data from a 4-year old
dual-core box over a 1 GB network to a VM reporting services box and
displays fancy charts in SSRS (not through MOSS) from a 70,000 row
database in about 5 seconds. We haven't tried connecting it through MOSS
yet.

Maybe we really are missing something. Can you please also let me know
if you made any configuration changes to achieve this level of
performance? Any insight into how you were able to get to this or the
specifics of your reports could really give me some clues.

Ssrs web does take ages to access normally I've noticed

Haven't tried adding it to warm up scripts but that may help