I think there's a clue in the diff. Because the "Could some admin from here..." paragraph contains ".sr", the diff algorithm thinks that paragraph was changed to "Biggest problem is ... [[:sr: ...", because they have the word "sr" in common (it's sandwiched between two punctuation characters in both cases). Then "Could some admin from here..." is interpreted as an added paragraph.

This edit [1] notified me, even though it's a just a modification to an existing post - one {{-}} template added, four newlines added, some colons removed. I had already been notified when that text was first added [2].

[1] https://en.wikipedia.org/w/index.php?title=Wikipedia:Village_pump_(technical)&diff=prev&oldid=727508339
[2] https://en.wikipedia.org/w/index.php?title=Wikipedia:Village_pump_(technical)&diff=prev&oldid=727418401

One more example from Redrose64:

Inconsistency - one fail, one success, little difference
This edit failed to notify me, but this edit did notify me, although there is no difference in the way that the user link and signatures are constructed.

@Lea_WMDE The examples in this task, might be helpful for your work.

Got another complaint about mentions not working from hewiki. Specifically, in this Flow discussion, there were several mentions and none of them worked: https://he.wikipedia.org/wiki/נושא:T8cxma4hu5m3kyww

There's a lot of mentions in there, but here are a few examples for specific posts:
https://he.wikipedia.org/w/index.php?title=%D7%A0%D7%95%D7%A9%D7%90:T8cxma4hu5m3kyww&topic_postId=t8e2fs6uwycfuugz&topic_revId=t8e2fs6uwycfuugz&action=single-view
https://he.wikipedia.org/w/index.php?title=%D7%A0%D7%95%D7%A9%D7%90:T8cxma4hu5m3kyww&topic_postId=t8e2akz7wyfawd3p&topic_revId=t8e2akz7wyfawd3p&action=single-view

Thanks @Quiddity for getting me in the loop. Will put the ticket in the sprint to see if this can easily be solved while working on our success and failure mentions task

Report of a false-positive Mention notification:

This edit notified me as a mention, this is correct behaviour.
This edit also notified me, but should not have done, since

• no new link to my user page was added, and
• no new signature was added either.
• The paragraph containing the link to my user page was altered in other ways, replacing "it" with "[[:sr:Медијавики:Common.css|it]] and other related pages".

I cannot determine why the second notification would have been triggered. It contradicts the three rules mentioned above, as detailed at https://www.mediawiki.org/wiki/Manual:Echo#Mentions

So I tested the first edit here and confirm that it does produce a mention as you said, woo!
https://en.wikipedia.org/w/index.php?title=User:Addshore/sandbox&diff=734136972&oldid=734136805

I also tested the second edit here and managed to reproduce the sending of the mention!
https://en.wikipedia.org/w/index.php?title=User:Addshore/sandbox&diff=734137661&oldid=734137561

The content of the mention event can be seen below:

a:4:{s:7:"content";s:495:"Could some admin from here or other user with bigger rights who knows how to deal with Common.css ({{ping|Addshore|Addless|Addbot}}) '''PLEASE''' update [[:sr:Медијавики:Common.css|it]] and other related pages on .sr? Many things are deprecated there, including even dotted lines being shown below sections. '''[[User:Addshore|<span style="color:black">·addshore·</span>]]''' ^{[[User_talk:Addshore|<span style="color:black;">talk to me!</span>]]} 11:21, 12 August 2016 (UTC)";s:13:"section-title";s:69:"Periodic table related templates /sr:Медијавики:Common.css/";s:5:"revid";i:734137661;s:15:"mentioned-users";a:2:{i:6569922;i:6569922;i:16447196;i:16447196;}}

Having spent the last weeks looking at the mention code lots looking at this diff I would except this to trigger a mention.

Things to note:

• Although the whole edit is classed as a change, the last line AFAIK will count as a signed addition (even though the same text actually existed in the old version)
• The signature that is checked is only ever ~~~ (timestamp is not needed and not checked)

Thus the parser sees everything that it needs in order to meet the criteria to send a mention. There is an addition, that ends with a signature, the signature matches the editing users sig, and the addition also includes user links.

So yes, this case aligns with exactly what @Catrope said above!

In T137755#2415795, @Redrose64 wrote:

This edit [1] notified me, even though it's a just a modification to an existing post - one {{-}} template added, four newlines added, some colons removed. I had already been notified when that text was first added [2].

[1] https://en.wikipedia.org/w/index.php?title=Wikipedia:Village_pump_(technical)&diff=prev&oldid=727508339
[2] https://en.wikipedia.org/w/index.php?title=Wikipedia:Village_pump_(technical)&diff=prev&oldid=727418401

This is exactly the same case, as you make an edit which moves a paragraph with your signature in it, the diff engine & discussion parser detect this as a new paragraph and thus the mention happens as normal.

In T137755#2493927, @Quiddity wrote:

One more example from Redrose64:

Inconsistency - one fail, one success, little difference
This edit failed to notify me, but this edit did notify me, although there is no difference in the way that the user link and signatures are constructed.

So the different that I notice between these two is your sig is different.
In https://en.wikipedia.org/w/index.php?title=Template_talk:Disambiguation&diff=prev&oldid=731304623 which failed your sig is missing the link to [[Wikipedia:Sig]].
The mention code checks for an exact match for your sig at the end of the comment, and if it is not an exact match then a mention will not be sent.
I looked at some of your other edits around that day and it seems the other sigs all include the link but I guess you removed it for this edit?

In T137755#2493956, @Mooeypoo wrote:

Got another complaint about mentions not working from hewiki. Specifically, in this Flow discussion, there were several mentions and none of them worked: https://he.wikipedia.org/wiki/נושא:T8cxma4hu5m3kyww

There's a lot of mentions in there, but here are a few examples for specific posts:
https://he.wikipedia.org/w/index.php?title=%D7%A0%D7%95%D7%A9%D7%90:T8cxma4hu5m3kyww&topic_postId=t8e2fs6uwycfuugz&topic_revId=t8e2fs6uwycfuugz&action=single-view
https://he.wikipedia.org/w/index.php?title=%D7%A0%D7%95%D7%A9%D7%90:T8cxma4hu5m3kyww&topic_postId=t8e2akz7wyfawd3p&topic_revId=t8e2akz7wyfawd3p&action=single-view

Unfortunately at this stage I haven't looked at how flow and mentions interact so I won't be able to diagnose this one! :)

In T137755#2493956, @Mooeypoo wrote:

Got another complaint about mentions not working from hewiki. Specifically, in this Flow discussion, there were several mentions and none of them worked: https://he.wikipedia.org/wiki/נושא:T8cxma4hu5m3kyww

There's a lot of mentions in there, but here are a few examples for specific posts:
https://he.wikipedia.org/w/index.php?title=%D7%A0%D7%95%D7%A9%D7%90:T8cxma4hu5m3kyww&topic_postId=t8e2fs6uwycfuugz&topic_revId=t8e2fs6uwycfuugz&action=single-view
https://he.wikipedia.org/w/index.php?title=%D7%A0%D7%95%D7%A9%D7%90:T8cxma4hu5m3kyww&topic_postId=t8e2akz7wyfawd3p&topic_revId=t8e2akz7wyfawd3p&action=single-view

I was just about to take a look at these but I will struggle massively due to language!
Is there any chance you could provide an english version of the wikitext @Mooeypoo ?

For Flow there is a default limit of 100 mentions, if over 120 mentions are attempted then only the first 100 will be sent.
Mentions of course can not be sent to anon users / ips or users that do not exist.
Other than that all mentions should really be sent.