Yes the relay will work, the Toyota Supra community does the same thing. I wouldn't bother with it unless you know everything else is working properly.
As mentioned "New" after market starters can be bad, so there is no guarantee that your new one is actually good. You can pick up an oem starter from a parts yard and rebuild it yourself, providing you can find all of the parts. The contacts are easy to come by, but worn contacts aren't always the issue w/starters going bad.