When I upgraded to Leopard I also bought an external harddrive for TimeMachine backups. Now, I want to use the drive with two different laptops and because it's quite big I also wouldn't mind keeping some space for a Tiger install to test my software on that. Reading the forums it became quite obvious that each TimeMachine backup should get its own partition, and here's where the agony began: How large should these partitions be? Yes, you can change partition sizes but if you want to keep the contents intact there are severe limitations. So, you starting thinking about the ordering of the partitions, too.
Luckily, I stumbled across another forum thread, in which people discuss copying TimeMachine backups. Somehow, maybe because of all the hard-link magic, I had assumed this wasn't possible but it turns out that the restore facility in Disk Utility can handle it. This means that even if you get your partition sizes wrong initially, you won't lose your backups when you change them later. You obviously need some temporary space somewhere else, though.
Oh, and if like me you did at some point delete that funny .000d8322fed6 (or similar) file in the root directory of your TimeMachine partition, help's here.