I've been using Time Machine from the time Leopard was released. Prior to that, I used the backup software that came with the .Mac (now MobileMe) service. I have an iMac with a 500G drive and, for TM, a 500G internal drive in an external case. My MacBook is similar but with 250G drives.
Prior to going Mac, I was running Linux and backing up using a routine I wrote, which used tar and gzip at its core.
I trust TM as a backup. It works, though its first months were, uh, "bumpy." Whenever I've needed to restore anything, I've had no problems. On times when I've needed to fully protect my hard drive, I've created a disk image with Disk Utility. Doing this you need to run DU from the installation DVD.