Now this may sound really simple, but somehow it's been bugging me for now, here's the code (explanation at the end):

void UMesh::GenerateBoundingBox(vector<MESH_STRUCT> &vertices)
{
	float maxx = 0, maxy = 0, maxz = 0;
	float minx = 0, miny = 0, minz = 0;

	FOREACH(vertices.size())
	{
		if (maxx < vertices.X || i == 0)
			maxx = vertices.X;

		if (maxy < vertices.Y || i == 0)
			maxy = vertices.Y;

		if (maxz < vertices.Z || i == 0)
			maxz = vertices.Z;

		if (minx > vertices.X || i == 0)
			minx = vertices.X;

		if (miny > vertices.Y || i == 0)
			miny = vertices.Y;

		if (minz > vertices.Z || i == 0)
			minz = vertices.Z;
	}

	// Set params
	BoundingBox.omx = BoundingBox.maxx = maxx;
	BoundingBox.omy = BoundingBox.maxy = maxy;
	BoundingBox.omz = BoundingBox.maxz = maxz;
	BoundingBox.ommx = BoundingBox.minx = minx;
	BoundingBox.ommy = BoundingBox.miny = miny;
	BoundingBox.ommz = BoundingBox.minz = minz;

	AdaptBoundingBox();
}

void UMesh::AdaptBoundingBox()
{
	BoundingBox.maxx = BoundingBox.omx;
	BoundingBox.maxy = BoundingBox.omy;
	BoundingBox.maxz = BoundingBox.omz;
	BoundingBox.minx = BoundingBox.ommx;
	BoundingBox.miny = BoundingBox.ommy;
	BoundingBox.minz = BoundingBox.ommz;

	// Apply Scaling
	BoundingBox.maxx *= scalation.x;
	BoundingBox.maxy *= scalation.y;
	BoundingBox.maxz *= scalation.z;
	BoundingBox.minx *= scalation.x;
	BoundingBox.miny *= scalation.y;
	BoundingBox.minz *= scalation.z;

	// Calculate size
	BoundingBox.sizex = BoundingBox.maxx - BoundingBox.minx;
	BoundingBox.sizey = BoundingBox.maxy - BoundingBox.miny;
	BoundingBox.sizez = BoundingBox.maxz - BoundingBox.minz;
}

UMesh is just a class. The GenerateBoundingBox gets all the vertices and then tries to get the max xyz, and the min xyz out of it. The BoundingBox.omx or .ommx is just backups for later use, omx = origional max x, ommx = origional minimum x (but it doesn't matter). From my results (i have a tree), the values are actually bigger than the mesh itself. The tree actually has submeshes so what I do is that I combine all the vertices into one vector. The AdaptBoundingBox is also used when scaling as the bounding box also then has to change when the mesh is scaled.

Now what on earth did I do wrong?

Well I changed it, but nothing really happened, same results:

float maxx = FLT_MIN, maxy = FLT_MIN, maxz = FLT_MIN;
	float minx = FLT_MAX, miny = FLT_MAX, minz = FLT_MAX;

	FOREACH(vertices.size())
	{
		if (maxx < vertices.X)
			maxx = vertices.X;

		if (maxy < vertices.Y)
			maxy = vertices.Y;

		if (maxz < vertices.Z)
			maxz = vertices.Z;

		if (minx > vertices.X)
			minx = vertices.X;

		if (miny > vertices.Y)
			miny = vertices.Y;

		if (minz > vertices.Z)
			minz = vertices.Z;
	}

Ohh sorry, this equals:

#define FOREACH(Arrmax) for(int i = 0; i < Arrmax; i++)

When I use these values, I add the current position of the mesh:

// Can we see it?
if (ViewFrustum.CheckRectangle(mesh->position.x + (mesh->BoundingBox.sizex/2.0f), // the x center
						   mesh->position.y + (mesh->BoundingBox.sizey/2.0f),  // the y center
						   mesh->position.z + (mesh->BoundingBox.sizez/2.0f), // the z center
						   mesh->BoundingBox.sizex, // the x size
						   mesh->BoundingBox.sizey, // the y size
						   mesh->BoundingBox.sizez) == false) // the z size
{FontSystem.get(0)->_string = L"Tree Available: false";return;}
else
{FontSystem.get(0)->_string = L"Tree Available: true";}

The frustum culling is based on the rastertek tutorial: http://www.rastertek.com/dx11tut16.html

It works, thanks!

These are the wrong way around:

		if (maxx < vertices.X)
			maxx = vertices.X;

		if (maxy < vertices.Y)
			maxy = vertices.Y;

		if (maxz < vertices.Z)
			maxz = vertices.Z;

		if (minx > vertices.X)
			minx = vertices.X;

		if (miny > vertices.Y)
			miny = vertices.Y;

		if (minz > vertices.Z)
			minz = vertices.Z;

When you init minx, for example, to FLT_MAX, you're never actually going to have vertices.x exceeding it. You need to check minx < vertices.x and maxx > vertices.x, and likewise for y and z.