Partial answer.
As you say, -nh- is quite a rare letter sequence within a word.
The word's metrical behavior suggests the division a-nhe-lo
The only perspective I can speak from confidently is a certain modern linguistic analysis of Latin syllabification (so, what follows isn't necessarily applicable to how you will see words hyphenated in songbooks, or how Ancient Latins described syllable divisions as working).
We can determine Classical Latin syllabification very straightforwardly if we take as an axiom the principle that only syllables ending in a short vowel are light. (See my answer to What makes a syllable "heavy" or "light"? and Alex B.'s answer citing Christian Lehmann.)
Using this phonological definition of a syllable, the first syllable of anhelo must end in a short vowel, as it scans as light in the poets:
- strictu|rae Chaly|bum et for|nacibu|s ignis a |nhelat (Aeneis 8.1.421)
This definition of syllabification therefore leads to the conclusion that anhelo in Classical Latin is divided into syllables as a.nhe.lo, even though it's unclear what it means phonologically or phonetically for a syllable to start with "nh". Personally, I'm inclined to the view that the natural pronunciation in Classical Latin was simply [aˈneːloː], i.e. without h and exactly as if it were spelled anelo, and that any pronunciations that did give "nh" a distinct value from "n" were as artificial as pronunciations of modern German gehen with an [h]. Michiel de Vaan says that there is no etymological justification for the presence of /h/ in this word, and suggests the spelling (and if applicable, pronunciation) with "h" is due to analogy from halare (Etymological Dictionary of Latin and the other Italic Languages, anhēlus, p. 43).
However, Priscian would divide it as an-he-lo
There are alternative approaches to Latin syllabification. The morphology-based rule that you mention (divide after a prefix in all cases) is in fact incompatible with the approach that I describe above (prefixed words such as inhibeo likewise scan in Classical poetry as if the h does not exist, and so would be syllabified as i.nhi.be.o according to my preferred system).
Priscian (fl. c. CE 500), who had great historical importance as an influence on how Latin was taught for many following generations, apparently argued that such words are or should be pronounced with aspiration, and that the syllable division should therefore come before the h:
nec in 'perhibeo', 'exhibeo', 'inhumatus', 'anhelo', 'inhibeo', 'adhuc', 'abhinc', et similibus secundae syllabae principalis aspiraretur vocalis, si terminalis consonans praepositionis in eam transiret, quomodo in 'istic', 'istaec', 'istuc'.
(Prisciani Institvtionvm grammaticarvm libri I-XII ex recensione Martini Hertzii, Heinrich Keil)
I don't consider Priscian particularly trustworthy when it comes to the pronunciation of "Classical Latin" (Cicero, usually taken as the model of a "Classical" speaker, lived half a millennium earlier), and he's obviously not an up-to-date source regarding the pronunciation of Latin in modern times either. However, the convention Priscian advocated for might be followed by some modern writers as an orthographic norm.