Wow! I got more than 900 songs searching for the title.
That was a bit too much to scroll through so I added the artist and searched for 'his eye is on the sparrow rozlyn sorrell'. The song popped up immediately on both the computer and iPad.
That was a lot to type into the iPad search box, making no mistakes, so I tried searching for Rozlyn Sorrell. I chose the quick complete when it showed up under the search box. There seems to be only one album, "I've Got to Sing My Song", and it's the first track.
I can't see any reason it would not show up for you.
All I can suggest is giving it another try.
Addendum:
Gifting just reappeared as a feature in the iPad's iTunes Store. I had not played with it since, so I took a look. From what I can see you can't gift individual songs unless they are singles. Every attempt I made resulted in gifting the entire album (which I carefully canceled before done). It's still possible to gift just one song in iTunes on the computer.