Hey StefanMF,
I do own a Redmi 3 (not the Note version but I guess it doesn't really make a big difference) and I had the same issue.
I bought it on aliexpress.com from a seller named "HongKongGoldway" at a really attractive price.
The problem is that this seller (among others I imagine) does not install the official Xiaomi ROM, but a custom one filled with bloatware, adware and other nasty stuff. I used it for ~1 month without any issue until ads came a few seconds after I unlocked the screen. And none of the mobile AV I tried found any malware.
The only solution I found is to format the internal storage and install the offical Xiaomi ROM, using xiaomi flashing software. I cannot give you full description about how to do it properly, but I can give you this tutorial I used :
Code:
http://xiaomitips.com/guide/how-to-flash-miui-fastboot-rom-on-locked-redmi-3/
The real problem is that the Redmi 3 has a locked bootlader, which means that you have to follow specific instructions in order to flash the phone without bricking it. (I don't know if the Redmi Note 3 has its bootlader locked too, but if it has you should be careful).
Anyways, you should try to find a tutorial which explains how to properly install official Xiami ROM on your specific phone model.
I didn't saw any ad or anything suspicious since I flashed mine. Good luck friend