It was a corrupt MXD.
I started a fresh MXD, added the data, and performed the same trace and the selection set results worked as expected.
I've been working with ArcMap for 5 years now, and it still amazes me how fragile the internal workings are. The bugs always seem to find me!
Anyways, hopefully this simple solution helps out someone in the future!