2008? More like the beginning of 2005. The EOS Rebel XT/350D replacement was the Rebel XTi/400D, introduced in mid-2006. The XTi/400D was replaced by the EOS Rebel XS/450D in early 2008.
I suspect your issue is that the cards aren't preformatted properly for the camera's file system and they are either too large for the camera to format them itself or they are formatted using a file system other than the needed FAT32. Most memory card makers at the time (SanDisk, Kingston, etc.) recommended cards no larger than 8GB for the 350D.
If you are trying to use CF cards larger than 8GB, you'll need to format them in a computer and create the needed file structure for the camera's operating system. If the CF card is already formatted using a file system other than FAT32 you'll need to use a computer to reformat the card using FAT32.
Instead of formatting in the camera, use your PC. As long as you use the correct file system (FAT32) and set up the needed folder structure after you format the card via the PC there should be no issues using the card. The reason almost everyone says to format in-camera is because that is the most user friendly way to guarantee the correct file system and folder structure.
- Be sure that the FAT32 file system is selected when the card is formatted.
- Label the card 'EOS_DIGITAL'.
- Manually create a folder in the root of the card named 'DCIM'.
- Then insert the card into your Rebel XT/300D and see if it is recognized.
More recent Canon cameras include instructions in the User Manual for how to properly format and set up the needed file structure using a PC.
Page 135 of the EOS 6D Instruction Manual explains how to create the needed folder structure and how to name folders. All folders with images must be created inside a folder named "DCIM". Basically each folder name must have 8 digits consisting of three numerical digits from 100 to 999 and five alphabetic (or _) digits. There can only be one folder that begins with any unique 3 digit number between 100 and 999, regardless of the five alphabetic characters that follow. You can have both a folder "100AAAAA" and "101AAAAA", but not both a folder "100AAAAA" and "100AAAAB".
One easy way to do this after the first time would be to erase all images on the card (which would leave the folder structure intact), copy the card's disc image to your computer, format the card on the computer, then copy the disk image back onto the card.