Thanks guys.
I found that messing with CLKPR messes with delay(), millis() and just about everything else. However, it's possible to 'fix' them by making a new boards.txt file with all the same details as your usual board, but with the correct clock speed in it (just use that stanza as your board - there's no need to burn a bootloader or anything - it seems that uploading a sketch is enough to specify the CPU speed). A bit of a hack, but saves having to put multipliers all through your code.
Now I've got to variable clock speeds, I'm thinking I should work out a low_power_delay() function for all those 50 and 100ms delays I'm ending up with. Even though clock scaling messes with millis(), I'm sure I can calculate compensation and end up delaying for the right amount of time. I'll put my thinking cap on...
I'll also look at dropping down to really low speeds for easy grunt work, and maybe going to 8MHz for VirtualWire or something.
Thanks for the help - I never did strip the chip down to the bare bones, but it's hard to improve on a current consumption of nearly zero!