According to the RadeonHD wiki page at X.org, XVideo support was added in version 1.2.2.

I currently have xorg-x11-drv-radeonhd-1.2.3-1.5.20081112git.fc9.x86_64 on a Fedora 9 system, running with a Radeon X34x0 (RV620). But I don't seem to have XVideo.

Does the XVideo announcement apply only to some other models of cards?