To begin this issue is version specific and has been addressed in 4.9.0 but there is still a bug in 4.9.1 which I will explain later.

The Problem

Assuming you have the banners module setup correctly and it should be rotating, as perhaps it does on your local machine. Then the issue the banners not rotating has to do with your servers performance not directly the configuration / programming of the banners module.

The details of the problem are:

DNN caches the last viewed banner's ID in RAM by way of the ASP.NET System.Web.Caching.Cache function. In the BannerController.vb it will then look to grab the last ID out of cache. If the cache is empty (more on this later) then it return a NOTHING object.

Here is where the version specific issue comes into play. Prior to version 4.9.0 if the cache object returned NOTHING then it would start with index of 0 for the banner rotation (meaning the same banner would show up every time).

Now for the reason why the ASP.NET cache object would return NOTHING?

I'm not 100% sure of the percentages but the problem is the Physical memory usage and Application Pool memory usage. If the Physical memory is within 10% of using all physical memory (bring up taskmgr and look at the memory. if it's over the amount of ram you actually have then you'll see this problem). ASP.NET will reject cache requests and begin garbage collection (deleting) what is currently in the cache. This will also happen if your application pool is within 20% of its own limit (If one is set).

In version 4.9.0 a randomize function was added when the cache object returned NOTHING. However a slight programming logic prevents it from including the last index for a banner in the randomizing so if you have 3 banners only 1 and 2 will show up.

NOTE: Because the banners module writes directly to ASP.NET's cache system. Changing the Cache Performance settings in Host Settings will not have anything to do with this.

Fixing the problem:
1.    Upgrade to 4.9.1 and get a mostly working rotator
2.    Wait for DNN to fix the fail over randomizer
3.    Modify the function manually

To fix the problem download the latest source of DNN 4.9.1
Under Library > Components > Vendor > BannerController.vb grab two functions (LoadBanners and IsBannerActive)
Add those two functions to Website > Admin > Vendors > DisplayBanners.vb

Find:
lstBanners.DataSource = objBanners.LoadBanners(intPortalId, ModuleId, intBannerTypeId, strBannerGroup, intBanners)
and replace with:
lstBanners.DataSource = LoadBanners(intPortalId, ModuleId, intBannerTypeId, strBannerGroup, intBanners)

Then if you want to fix the randomize issue

Find:
intLastBannerIndex = RandomGenerator.Next(0, arrBanners.Count -1)
Replace with:
intLastBannerIndex = RandomGenerator.Next(0, arrBanners.Count)

With regard to your explanation of why the cache expires, you are correct, although in my experience the "scavenging" occurs at a much lower %.

The ASP.NET Cache is scavenged before other memory, and in my experience occurs when ~50-60% of physical RAM is being used.

Okay back from testing.

The fix should definetly work. The Random.Next function second paramater of maxValue is the number of possibilities which is also 0 based. So an array of 3 items would return array.count=3 which is 0,1,2 and the random.next(0,3) has three possibilities, again 0,1,2

I wrote a quick console app to make sure. Running this indexId will never return a 3.

 Random randomize = new Random();
            int indexId;
            int i=0;

            do
            {
                indexId = randomize.Next(0, 3);
                System.Console.Write(indexId + ",");
                i++;

            } while (i < 800);
            Console.ReadKey(true);