“Not soul” is actually an incorrect translation of anattā. I recently had cause to correspond with Prof. Richard Gombrich on this topic as I had mistaken a negated past participle for an example of a negated adjective in an article I submitted to him. He kindly pointed out my mistake. In the cited phrase from the Dhammapada, anattā is an adjective (a bahuvrīhi compound) and it has to be read in this case as “without attā”
I think most scholars now accept at “attā” here is a reference to the Vedic ātman, which in turn references the Vedic belief that there is a reality beyond our senses which consists of absolute being. Also known as brahman. To call ātman a “Soul” would tend to imply an individual soul, as per Christianity, but the Vedic absolute being obliterates the individual which merges into the absolute and loses all trace of individuality. “All is one” as the Hindus say, and they really mean it.
So “not soul” is no better than “no soul”, in that it is both an incorrect and a misleading translation. This is an example of the failure of purely semantic methods for understanding a foreign literature (I’ve been intensively working on another these last two weeks that ought to appear in print in a few months). What provides the continuity between lives in Vedic belief is absolute being - the whole phenomenal world, including all the people, is an illusion and once you get rid of the illusion there is just brahman. It is in some respects similar to the puruṣa of Sāṃkhyadarśana.
The problem never was the existence or non-existence of anything. It was that people who came to Buddhism looking for absolute being (or absolute truth or reality, since sat can translate them all) would be disappointed (dukkha) by examining their experience: since experience changes all the time, one will never find absolute being in experience. Absolute being cannot change or it wouldn’t be absolute.
It is purely conjecture on my part, but I suspect that non-Buddhists who achieve cessation both then and now often mistake nirodha for contacting the absolute. It has in late Vedic terms three characteristics: saccidānanda: being (sat), awareness (cit), and bliss (ānanda). And since in cessation, nothing is arising and passing away, one can easily mistake it for the absolute (if one believes in such a thing). One of these days I’ll try to make the case more formally.
So I hope this is clear. In this Pāli phrase anattā is an adjective (a bahuvrīhi compound) that means “without ātman”, where ātman has to be understood as it is defined in the Bṛhadāranyaka and Chāndogya Upaniṣads, i.e. as absolute being. It would be good to get everyone on the same (the right) page before beginning yet another interminable discussion of “self/soul” in Buddhism.