tl;dr
It seems this is an issue specific to some Samsung Galaxy S-series devices running Android 5.1.1 Lollipop. There's nothing we can't do other than waiting for update from Samsung (if it's really a bug).
I believe it's either a bug, or Samsung's decision to remove "Direct Message" widget (for unknown reason) from their Contacts app. There were some reports about this issue.
From a post on AndroidCentral forum,
I've been trading support emails with the Nova folks. According to them, "Samsung removed the direct dial shortcut for no apparent reason in their Lollipop update. It is also missing from the TouchWiz launcher."
Another thread also asked the same issue,
I just upgraded to the S6 and it has Android 5.1.1.
There are a few things I can't figure out.
[...]
3. How can I set up Direct Dial shortcut on home screen and Direct Message? [...]
And lastly, on T-Mobile forum which gives hint on not carrier-specific,
My wife and I both have the S5 on 5.1.1 (F0G6) and both have this problem since the update. It happens for Direct Message shortcuts/widgets too. It appears to be a TouchWiz bug (guessing) since changing Launchers to something like Nova keeps the shortcut ... It is a small thing but a big problem for me - help!
My best friend has Verizon, and hers are disappearing as well, so I don't think it's a T-Mobile issue, I think it's an OS issue.
Which was replied with,
This is a known issues. Both T-Mobile and Samsung are trying to find out what is causing it and fix
