Having spent fifteen years working with both Notes and Exchange (from 1998-2014 - didn't quite get sixteen years!) I'm a little surprised to read this.
I'd venture to suggest that any admin who said that isn't a Notes admin, but instead a Windows admin who was forced to work with Notes and had no training in it - or willingness to learn.
The major problems are usually ID files and a lack of AD integration. So yes, user administration has a couple of challenges - but later versions of Notes have an ID Vault which helps a lot with that. And even earlier versions (6 onwards?) had password recovery, which also helps a lot - just generate a recovery key and start using it, and your helpdesk will be able to reset passwords much more easily.
User administration around ID files was certainly the weak point.
But the server itself was solid, capable and had a lot of great options. Its handling of storage, mail routing, and replication was generally much better than the competition. For example in a multiple site, WAN-linked environment moving users around is a snip - and very reliable compared to Exchange, which often fails repeatedly on bigger mailboxes. (I've actually had to resort to exporting a mailbox and transferring it as a PST using Robocopy, then moving it re-importing the data!)
I'd definitely agree that at the SMB level Exchange is better due to its integration with AD. But frankly, that market is being ceded to the cloud anyway. However, as your system grows in scale, Notes definitely starts to be much more attractive to administer. It's not without some faults, but I've seen far worse products - and I much preferred administering large Domino environments to large Exchange ones.
I'm more surprised that you found people who liked the user experience - that was what I usually got complaints about!