I would like to get into doing orientated box/terrain collision,
so I have to calculate the terrain face normals their plane equations
every frame for the box's points. Instead of doing the calculation
over and over again, I would rather cache it, and have the opportunity
to retrieve it if it was still valid.

What do you cache, how much of it do you cache, and do
you have any special or fast way of storing and retrieving the data?
Is cached data just simply stored as an array of data structures?

Basically I'd think what you're looking at is the same as marking "dirty" rectangles in DX. i.e. you update the view ONLY in rectangles marked "dirty". You have the option of doing the entire thing ofcourse!

Now, I would think since every frame only some of your data will be changed, you'd need a way of storing this so that you can easily mark "dirty" regions.

My thoughts on this are...
Possibly storing the terrain in an explicit tree structure, with a field for marking the nodes as dirty. Then as you do whatever you're doing, if a tree node is marked dirty, that node and all it's children are recalculated, otherwise you leave it be.

If your heightmap was small, you could easily precalculate and store
terrain collision data within the structure. But in my case, that is
not possible, because it would take up too much memory. That's why
I would like to cache it so I can use it later.

So for example, if I had I tank, that didn't move much or moved slowly
over the same area, I could easily recover the cached data instead of
calculate it again. If the tank moved fast over the terrain, the cached
data probably wouldn't be very useful, since it would be replaced with
newer data quicker.

I've come up with some possible solutions:
1. Store data in simple allocated array. Search for data by looping
through all of them if necessary.
2. Store data in a dynamic linked list. Insert them in a MRU list
order fashion (MRU at the top of the queue) and loop through all
of them if necessary.
3. Hash the data.