I've been wondering the same thing...if I don't *need* the incremental backups then I plan to start a new backup (archiving the old one) since this seems easiest and is sure to work.
I should mention that I use the same disk for other things too, so freeing up space is a consideration for me.
I think that Apple recommends dedicating a drive or partition to Time Machine, and generally avoiding use of that partition for regular storage.
I have seen a tip to the contrary that is advertised on the Apple support forums, though-- cloning the Leopard install DVDs on the Time Machine backup drive, in case the DVDs end up scratched or lost and you need a full restore.
******
ADDENDUM: Here's my Time Machine setup, as an example. I have an iMac with a 250Gb hard drive with two partitions: a ~165 Gb partition for Mac OS X and apps and a 64Gb NTFS Bootcamp partition for Windows.
Attached to the iMac is a 250 Gb Western Digital external HD, attached via FireWire 800 for maximum speed. That external HD has three partitions: 150 Gb dedicated to Time Machine, 50 Gb or so for extra Mac OS space, and a 30 Gb FAT32 partition that both OS X and XP can read and write.
The Time Machine drive has only 4 Gb free right now. I know that some Time Machine consolidation has happened, since, when I checked it the other day, it had less than 1 Gb left. My main Mac OS X partition only has 75 Gb used.
Nevertheless, since I have the other partitions to work with, I don't have to worry about running out of room for my other "stuff," and I can
still go back to late 2007 to restore, when I first got my iMac. That's how optimized Time Machine's consolidation algorithms are.
My recommendation (take with however many grains of salt as desired): If you're comfortable with starting all over with Time Machine, then do so with an external hard drive that has more than one partition. Dedicate a good-sized chunk of it (approximately the size of your main OS X drive or more) to one partition for Time Machine, and use the rest for other storage. Before turning Time Machine back on, try to move very large files (uncompressed audio, movies, etc.) to the secondary partition if feasible so they don't clog up your Time Machine from the get-go.