In short, here’s how it went down:
I installed Brave on my private computer, enabled Brave Ads and went on to use it normally. I received ads for a few days, and then it all suddenly stopped right around when I added my iOS device to the sync chain. It was rather weird but I kept using it hoping that it would come back to normal.
A couple of days ago, I added my work computer to the sync chain as well and it not receive ads either. I gave up even thinking about Brave Rewards, but then magically, this morning I decided to give it a try once again and removed my iOS device from the chain, just to be sure, since it can’t get rewarded for ads anyways (even though that is the only device where I was seeing ads). All of the sudden, 10 minutes went by and my work computer started seeing ads again!
Naturally, I checked everything there is on the forum and tried everything I could (even https://www.bennish.net/web-notifications.html), it did not seem to work on my private computer. But when the work computer started seeing ads again, just because I removed preceding iOS device from the chain, now that was an odd behavior I needed to report.