Why do you suppose it's some kind of an “app“ that “appeared“ at all? “SIM toolkit“ is just a user interface (yet implemented as a system app on Android) for apps stored on the SIM, so-called Cardlets made in a pretty scarce version of Java: Java Card. This technology exists for decades, from times before the mobile internet and even before the WAP, and UIs for it exist even in the most basic phones. Mostly, the SIM Menu cardlets are just catalogs of USSD requests, which you can manually invoke from a dialer if you find a list on your operator's site or somewhere. These requests may get a response, paid or not paid, depending on the service. Some people may still prefer such services, as they have a completely Push nature and conserve battery by not requiring Internet connections, and are available even on basic phones. By removing the “SIM toolkit“ app you did not remove the cardlets anywhere from your SIM, you just got rid of the middleware to access them. It's like, well, willing to remove the Settings app because it annoys you by its existence.