It would be nice if there was an Application.UseMoreMemory() function that we could just call :-)
Alas, I know of none.
All the docs I've seen say that it's limited by memory, but it's not physical memory that's the issue, it's the virtual address space you have available to you.
You should keep in mind that, while the increase from 500 to 600 only looks like a moderate increase (though 20% is large enough on its own), because you're doing that in three dimensions, it works out to be close to double the storage requirements.
From memory, Excel 2007 used short integers (16 bits) for boolean type so, at a minimum, your 5003 array will take up about 250M (500x500x500x2).
Increasing all dimensions to 600 would give you 600x600x600x2, or about 432M.
All well within the 2G usable address space that you probably have in a 32-bit machine (I don't know that Excel 2007 had a 64-bit version), but these things are not small, and you have to share that address space with other things as well.
It'd be interesting to see at what point you started getting the errors.
As a first step, I'd be looking into the need for such a large array. It may be doable a different way, such as partitioning the array so that only part of it is in memory at any one time (sort of manual virtual memory).
That's unlikely to perform that well for truly random access but shouldn't be too bad for more sequential access and will at least get you going (a slow solution is preferable to a non-working one).
Another possibility is to abstract away the bit handling so that your booleans are actually stored as bits rather than words.
You would have to provide functions for getBool and setBool, using bitmask operators on an array of words and, again, the performance wouldn't be that crash-hot, but you would at least be able to then go up to the equivalent of:
' Using bits instead of words gives 16 times as much. '
Dim arr(8000, 8000, 8000) As Boolean
As always, it depends on what you need the array for, and its usage patterns.