aahhh, i have spent the best part of two months trying to work out if Joomla is worth using from an SEO stand point. I have tried the shsef404 plugin which you will be recommended. But I just don't find it very SEO friendly. I implemented some hacks regarding nofollow tags so there are away around the limitations.
I did a few blog posts around my experience with joomla. I won't drop a link as that looks like shamless spamming and I know its frowned upon on here.
But just to give another source for good infor
Joomla Search Engine Optimization, Training and Templates - Alledia.
You can PM me if you want a link to the blogs posts I did on my experience with Joomla. I have decided to just use Wordpress and Xsitepro2 for any sites I put up. But I won't be putting up any large dynamic sites so that may not be suited to your work.
Cheers
Kieran