My experience has been that they come back even after I've emptied the cache, unchecked the box that says to keep it up to date etc. I disable the app and it's back, sometimes in 1/2 hour, sometimes the next day. This has been mostly true with Samsung Apps I'm not interested in. But I'm not talking about anything anyone could possibly deem "essential".
I noticed that the window that "allows" you to disable, such as the Travel App also says at the bottom "Launch by default". It sounds like the app will relaunch the first chance it gets. Any idea where the defaults are managed?