Stop shouting (we're trying to help, and I didn't miss the point, thanks).
Are you using the same theme for all sites? If not, then no matter WHERE you put the ad, it might not work on all sites. You could end up breaking someone's site down the line.
On the other hand, if every site has the same theme, or one of a few listed themes, you can still manually edit each one for optimum layout. Gives you more flexibility. 10,000 sites not-withstanding, you may not want the exact same style of ad per site.
And you never answered "Where ELSE outside of the theme were you TRYING to put it that it was failing?" I didn't want to retrace steps you'd already done.
If you do it via a homegrown plugin, put it in the mu-plugins folder. I actually DON'T recommend that, as not every theme will work equally well. If it's a site where you are always going to control the themes, then sure, it could work, but you'll have to test each theme to make sure layout is correct.