When the starter goes out, is it typically because just the selonoid has gone bad or has the starter had it too? The reason I am asking is that the starter I pulled is in very good shape with on 45k miles on it. Do the brushes, etc go bad with time and it is recommneded to replace both all the time.

At 45k, it ain't new.

Take it out and take to a parts store that has testing equipment...here in Texas, Auto Zone will test starters and other electronic equipment for free.

I never replace the starter without also getting a new solenloid...like a heater hose...replace one you might as well do the other.