Modifying a Visual Tree/ControlTemplate

I'd suggest you consider using a ControlTemplate -- they're easier to manage, make your control more stylable, and don't rely on the ControlTemplate 'being' a certain way. By that, other than a specific "PART" that might be required such as the text editing features of a text box, you don't need to assume the existence of any particular element within the ControlTemplate.

<Style x:Key="MyAdvancedTextBox" BasedOn="{x:Null}" TargetType="{x:Type local:MyTextBox}">
<Setter Property="Foreground" Value="{DynamicResource {xtatic SystemColors.ControlTextBrushKey}}"/>
<Setter Property="Background" Value="{DynamicResource {xtatic SystemColors.WindowBrushKey}}"/>
<Setter Property="BorderBrush" Value="{StaticResource TextBoxBorder}"/>
<Setter Property="BorderThickness" Value="1"/>
<Setter Property="Padding" Value="1"/>
<Setter Property="AllowDrop" Value="true"/>
<Setter Property="FocusVisualStyle" Value="{x:Null}"/>
<Setter Property="Template">
<Setter.Value>
<ControlTemplate TargetType="{x:Type TextBox}">
<Grid Background="{TemplateBinding Background}">
<Grid.ColumnDefinitions>
<ColumnDefinition Width="0.859*"/>
<ColumnDefinition Width="0.141*"/>
</Grid.ColumnDefinitions>
<ScrollViewer SnapsToDevicePixels="{TemplateBinding SnapsToDevicePixels}" x:Name="PART_ContentHost" Margin="2,2,0,2"/>
<Ellipse Fill="#FF0BAEE5" Stroke="#FF000000" Margin="4,0,0,2" Grid.Column="1"/>
</Grid>
<ControlTemplate.Triggers>
<Trigger Property="IsEnabled" Value="false">
<Setter Property="Foreground" Value="{DynamicResource {xtatic SystemColors.GrayTextBrushKey}}"/>
</Trigger>
</ControlTemplate.Triggers>
</ControlTemplate>
</Setter.Value>
</Setter>
</Style>

The above just is a simple control template with a grid and an ellipse, along with the text editing features of a text box defined as the PART_ContentHost.

If you follow the instructions near the bottom of this article, Control Authoring Overview, you should be well on your way to having the control you want.

If you try to get access to the default visual tree and modify it -- you'll need to adjust the behavior based on each theme WPF supports now and in the future. (For example, some Vista controls use "Chrome" while XP styles use standard borders or other special FrameworkElements).

You're right, it is just the text box, and yes, it is dependent on the theme -- but the article I pointed to describes how to handle the multiple themes that could be installed and have a fallback available.

I added an ellipse to the textbox box representing 'anything'. It could be an image like in your code, or a button, or anything. You can attach event handlers, commands, etc.

Without having exacting knowledge of the visuals of the controls, you can't just 'add to them'. For example a text box doesn't have a grid in it by default. It only has a border, which only supports one child. So, you'd have to remove some visuals, add new ones ... again, relying on internal knowledge of how the control was constructed. Most controls don't have any extra Panels for layout. You can't just add a new header to a list box without changing how it's built.
By deriving from TextBox, creating YourTextBox, and doing a custom control template, you get the best of both. You control the visuals, you get inheritance and all the properties, but you can also add new Commands, etc. to add functionality. The only downside really is being theme aware as far as I'm concerned. Being able to do "control is TextBox" can be very useful. A UserControl wouldn't give you that.

Doing your own UserControl would be a lot of extra work as you pointed out if you want it to really "be" a textbox with properties and such. If you want to be lazy, you can expose the internal textbox as a property -- but that's not a good design -- just functional.

Control containment in a usercontrol (or other control) may introduce focus issues that would need to be handled in code -- controls not getting focus, etc.

I fixed the link -- for some reason it had http:// ...

My example works fine -- I'm not sure what Border you're talking about though? I purposely used a grid rather than a border inside the textbox as I wanted to lay the text editor area out with an ellipse as I mentioned. I could have added another border around the text field - yet that border wouldn't necessarily have encapsulated the ellipse.

This is a great example of where you shouldn't assume what is in a ControlTemplate unless you authored it. Things changes. Microsoft could change the visual templates to be more efficient (for one, I hope they do with textboxes as they use a lot of visual elements when they aren't active!).

Of course, you can go either way you want with your design and implementation. I'm just suggesting the way that I believe Microsoft intended control authoring to work.

You'll need to work with a few methods and overrides the other way:

VisualChildrenCount
GetVisualChild
AddLogicalChild
AddVisualChild
MeasureOverride
ArrangeOverride

There may be a few more that I've forgotten -- but if you search for either of the first two methods, you should be on your way.