This article is from the CD-Recordable FAQ, by Andy McFadden (firstname.lastname@example.org) with numerous contributions by others.
First off, see section (3-40) for an explanation of the different ways to
make a disc look empty. For conventional CD recording, you don't want
to format the disc at all.
If it's a CD-RW that you've used before, try erasing it first. If you
can't seem to do that either, see section (4-27).
One user with DirectCD 5.01 had troubles that went away by changing the
VCACHE settings from min=2048 max=6144 to min=0 max=10240. See section
(4-1-2) for information about the surprisingly important VCACHE settings.
It has been reported that some virus scanners, notably TBAV, can interfere
with the format process and should be disabled.
This was sent to me by Jac Goudsmit, regarding formatting CD-RW media
with DirectCD for Windows 2.0a:
"When [Roxio] DirectCD refuses to format a CD-RW for packet-writing, it's
possible that the disc is not completely blank. This may happen because you
chose the "quick" option when you last erased it. The quick-erase option
only erases the lead-in area to make the hardware and software think the
disc is empty. This is fine if you're going to use the disc for "normal"
writing as a CD-ROM, audio disc or whatever.
The packet-writing formatter in DirectCD 2.0a however (apparently) requires
the disc to be totally empty, so you really have to do a full erase if the
disc contained data previously.
BUT: there's another problem: after you do a full erase and shut down the
program you erase with (e.g. EasyCD Pro or Easy CD Creator) it's possible
that the DirectCD program won't recognize the disc as valid media, and you
still won't be able to format it, until you restart the computer.
Unfortunately this means that if you want to start using a previously
recorded CD-RW for packet writing, you'll have to wait a total time of at
least an hour and a half for the erase and format to complete..."