Getting toast message with text sending
Turns out that it was the Sim ToolKit that was showing the toast notification. I have recently switched to a Reliance Jio Sim (India), which has free unlimited calls and 4G data until December! Now that is too good to believe and fishy.

I used this app: https://play.google.com/store/apps/details?id=com.coconuts.pastnotifications&amp;hl=en
And allowed it to monitor the Toasts via Accessibility settings.

For now I have Force Stopped the process. The toasts are gone, should they come back, I will disable the Jio Sim itself.