I am having the exact same problem. Brand new (36 hr. old) Kyocera Hydro Wave from MetroPCS with Android 5.1. It took a while but I was finally able to establish that if an app has been moved to the SD card and the phone is restarted, any icon/shortcut on the home screen(s) disappears. The app is still in place on the SD card (16GB in my case; same one I was using in previous Hydro XTRM) and will run just fine if selected from the Apps menu.
If I move the app back to internal memory, I can place an icon/shortcut on the home screen(s) which will survive phone restarts. If I move it back to the SD card again and put an icon/shortcut on the home screen(s), it will disappear after the next phone restart. Completely repeatable.
I even bit the bullet and performed a factory data reset (throwing away many hours of work I had put in installing numerous apps and their associated data last night). The same behavior still occurs even in a factory default configuration with only one downloaded app moved to the SD card.