but as soon as it is plugged in, the computer is running the index and blocking attempts to add it to privacy
Did you see the section of the FAQ that pointed out the anomalies from stopping indexing with Privacy on external volumes?
Check the FAQ again and try the instructions under "Disabling Spotlight Indexing while Indexing is in progress"
Also, you didn't say whether this drive moves between different computers, but if it is used only on OS X 10.4 systems, you could just let it index-it should only need to do it once.
The problem with external drives arises when moving between Spotlight and non-Spotlight systems. Externals are reindexed at a point when the last mounted time varies more than a specified threshold from the last index modification time. If the drive is used only on 10.4 systems, even if not the original system, the index will be updated normally since the index files are stored locally on the volume.