Hi @_drin, Sim ToolKit app would really disappear if your sim was turned off or removed and would take some time to (which I think depends on the sim?) be recognized by the phone again.
You can replicate the concern again by turning Airplane Mode to ON and you'll notice that after a minute (or two) Sim ToolKit app would disappear. Same goes with you're contacts.
As for the other apps, if there are any, the only known reason why they won't appear right away after you restart your phone is if the app was moved to SD card, like what @SoloRazr mentioned.
As for fixing, I'm not really sure if this requires "fixing" since I've encountered the sim-contacts-sim toolkit behavior since JB 4.2 but have you tried re-seating the sims? Also, are you using an old sim which was cut and not pre-cut to fit AF2?