On discovering that my server does indeed have mod_rewrite (didn’t have time to look before) I have now changed the permalink structure within the blog. The new format (/year/month/date/post-slug) gives much more information about the post than the old one (a question mark followed by a number), which apparently is not very well liked by search engines.
Thanks to Wordpress’ brilliance, it doesn’t even break the old structure: any old-structure links (e.g. in trackbacks I sent to other sites) will still work perfectly, but the site itself will now display, use (and send, via trackbacks/pingbacks) the new format.
EDIT: You can also use this to access yearly, monthly and daily archives. Simply remove the section that you do not want from a permalink. For example to view the archive for 31st May 2005, go to http://www.davidarussell.co.uk/2005/05/31 .