Hurray... Finally got hold of the culprit.
It was named com.scloud.... (Didn't remember the full name)
Initially thought it was system app but when going thru all suspicious names found that there is an option to uninstall which is not available for sys apps.
After I installing it alk these ads are gone.
Sent from my GT-N7100 using xda app-developers app
Samsung Galaxy Note II N7100
Samsung Galaxy S GT-I9000