Hmm. If GetAvailableTextureMem really returned a wrong value with your 3D card, then the error message could be correct and you're in fact exceeding the memory. What 3D card are you using? Just to be sure, can you run a simple test like this?

Code:
void main()
{
	fps_max = 60;
	video_mode = 6;
	int i;
	for(i = 0; i < 10000; i++) {
		wait(1);
		BMAP *Bmap = bmap_createblack(1048,1024,32);
		draw_quad(Bmap,vector(10,10,10),NULL,NULL,NULL,NULL,50,0);
		draw_text(str_printf(NULL,"d3d_texfree: %d MB",d3d_texfree),20,60,COLOR_RED);
	}
}


At some point this will exceed either the available video memory or the available system memory, and the texture creation will fail. Does d3d_texfree then really display still your full 4 GB?