Does my song have to be released by a record label for me to receive payment from STIM when the music is played on YouTube?
Yes, it has to be released by a record label or an aggregator. It is their responsibility to provide a recording of your song to YouTube, a so called reference. This is required in order for YouTube to be able to identify your song via their automatic matching system, and it is therefore not enough for the song to be registered with STIM.
Video clips containing music that do not automatically appear in search results can sometimes be matched manually. The minimum requirement for this is 100,000 views in one month, in one single country. You can also read about the general limit for the number of YouTube views required for you to be entitled to payment.
YouTube also has a list of their certified artist service providers.