Right off the bat, I'd say option 1 is good:
1) Create an attached property to hold the WatermarkText that you can use on AutoCompleteBox.
2) Create a control template for the AutoCompleteBox (simply copy the existing one using blend), but change the TextBox to a Watermark TextBox, and use a TemplateBinding to set the WatermarkTextBox's property to the value of the attached property.
The control template should be applied in a style (for example WatermarkedAutoCompleteBoxStyle).
You should be good to go with that.
Any time you want a watermarked autocomplete box, just set the attached property value and apply the style you defined.
If you need more in-depth explanation of one of those steps, just raise your hand and I'll try to find the time to create a sample.
Alternatively you can derive from AutoCompleteBox, add a DependencyProperty instead of an attached property and package the style in the Themes/generic.xaml file, but I usually do it once it works.