For the sake of continuity, I'll summarize the end of my problems. My brother came over and I was finally able to test voltage at the starter wires. The constant 12V wire directly from the battery read 12V, and when cranked (or when the relay was jumped and the ignition turned to ON), the other power wire read 12V as well. So, the starter was getting 12V and 12V all along. Took the starter to a DIFFERENT advance auto, and it failed all the tests.

Purchased a new starter, and problem was solved. Just don't know why the first auto store said the starter was good...I even saw it run on their machine, so there were no indications the starter was bad. Just a strange situation! Thanks for all the guidance everyone!