That's quite a hard question to answer as it depends on your requests/second and whether your server can handle it

As a general guide, I personally would probably implement a caching system if the site where getting more than about 10 requests per second or less if the site was paticularly server-intensive.

As for memcache, I've never used it so I can't really comment. I have used APC though which I liked a lot - worked well.

Alan