Wouldn't call myself an expert by any stretch, however, I've have set up and still run a few Magento stores.
The reason I asked which version your site is running, is because I believe they rolled out the 301 option in version 1.4.2.0 (based on the release notes I checked). Definitely strange you don't see it when using version 1.5.1.0.
You can solve it instead, as you rightly point out, using a rewrite rule in .htaccess, like the second extra rule from the Creare article:-
RewriteCond %{http_host} ^yourdomain.co.uk [NC] RewriteRule ^(.*)$ http://www.yourdomain.co.uk/$1 [R=301,NC]
I don't usually find I need this, because Magento solves the www issue with that 301 dropdown menu option which is missing for you.
I don't generally need the first extra rule from that article, either:-
RewriteCond %{THE_REQUEST} ^./index.php RewriteRule ^(.)index.php$ http://www.yourdomain.co.uk/$1 [R=301,L]
When I switch on Web Server Rewrites in the Magento backend, and correct the Magento root (if necessary) in .htaccess, as described in that article, the removal of index.php from URLs is usually solved. If you do still have the index.php problem, however, you could solve it in .htaccess too.
I'm definitely not an apache/mod_rewrite expert so I can't vouch for the syntax necessarily, however it certainly looks correct.
If I were you (or your client), I'd also want to get to the bottom of why I don't see that 301 option in Magento, as it could be symptomatic of an incomplete upgrade in the past. It could of course, be something else obvious which I'm missing - definitely worthy of further investigation though.