Fairies disappear after the thing they embody disappears. So after all the ice melts, Cirno will cease to exist.
Gods aren't immortal either. They're like youkai- once people lose faith in them, they cease to exist. That's why Kanako went to Gensokyo in the first place- people in the outside world are losing faith in gods, so if she doesn't find some other source of faith she and suwako will disappear.
Eiki and Komachi aren't immortal either. They're essentially like any other god or youkai. Long lived, but they can still die or be killed.
And no one in the SDM is immortal.
Basically, very few characters in touhou can be considered truly unable to die. The only ones I can think of are the hourais and Yuyuko, and I don't think Yuyuko really counts as "immortal" for obvious reasons.
That said, Purvis might actually be right. The Dragon God is a freaking dragon which, as we know, have brilliant barrettes that make them immortal.