I don't have deep enough understanding so I'm just throwing ideas around here. But there must be a way to distribute the count of the running nodes in trustless manner (similar to how the blockchain is distributed) without every wallet having to go and ping every masternode. This would obviously mean that the implementation wouldn't be so straightforward anymore.

And, the count is needed only before doing the denomination, which could be once a day, or once a week for most users.
I'll but in with my thoughts on that, if I may:
You'd have to get the MasterNodes to do the consensus finding, as you don't want to have a scenario where individual nodes can be enumerated (eg. by them randomly pinging 2 MasterNodes and then finding consensus with their peer group). The problem is that a superpeer group broadcasting consensus is still effectively centralised (eg. what's your outlier cut-off for network state among the superpeers? well, then that's all that's needed to confuse consensus...whereas with Bitcoin you need to own 51% of the network). It also doesn't let you know if a compromise event occurs. If, for instance, there are 50% of the nodes hosted on Amazon infrastructure (a likely event if the resources required exceeds that available in most virtualised environments), how would you know if Amazon was subpoena'd and the FBI or the NSA or whoever had access to >50% of the MasterNodes? Knowing their up/down status is one thing, knowing if the host OS their VPS is running on is compromised or not is another entirely.