Note To install Windows Search 4.0 successfully on a computer that is running Windows XP or Windows Server 2003, Terminal Services must be running on the computer. Also, Terminal Services must be running for Windows Search 4.0 to function correctly.
I read the first part of the quote as only applying to XP or Server 2003. Meaning, to
install it on those systems, TS must be running. In order to
use Search 4.0, TS needs to be running on all supported OS's, including XP/2003/Vista.
I could have read too far into it, but that is my take, at least.

BV Edit: Bad quote formatting.