Also,
1. How 'new' is your battery? Is it sealed or require topping off? What is the "resting" voltage?
2. Have you ever serviced/cleaned your starter motor's gear drive and lubricated it?
While my first guess would also be the starter relay, it *might* possibly be either:
1. Battery getting a little weak and dropping in voltage when the high current demand of the starter is required -> drop in voltage is sometimes dropping low enough that it is insufficient to keep the starter coil energized enough to "pull in" the relay, or
2. The starter motor gear set can be dry and binding sometimes. This causes the starter to almost lock up/bind, causing huge current draw and dropping the battery voltage, which again causes starter relay coil to drop out, etc.
Always start with the easiest thing first. So I'd stick with the suggestion to try the relay test first. If that doesn't seem to change the behavior, though, look to these other possibilities.