답변의 답변을 보다 보니 궁극적으로 원하시는 바를 알겠기에 다시 답변답니다.
아래와 같이 하시면 원하는 결과를 얻으실것 같네요.

예전 자게에서 Nibble 님이 올리신 중복 없는 난수 추출 코드를 약간 손봤습니다.
(어떠한 일로 삭제되긴 했지만...)

속도도 제 컴퓨터 기준 0.3~0.4초 정도 걸리고, 메모리도 386mb 밖에 안먹네요.

struct PHONENUMBER {
	short f,r;
	AnsiString GetNumber() {
		AnsiString s;
		s.printf("010-%04d-%04d",f,r);
		return s;
	}
};


void shuffle(PHONENUMBER* items, int count, int totalcount );
void swap(PHONENUMBER &a, PHONENUMBER &b);
//---------------------------------------------------------------------------
void shuffle( PHONENUMBER* items, int count, int totalcount)
{
	Randomize();
	for( ; count; --count )
		swap( items[Random(totalcount)], items[--totalcount] );
}
//---------------------------------------------------------------------------
void swap(PHONENUMBER &a, PHONENUMBER &b)
{
	PHONENUMBER tmp=a;
	a=b;
	b=tmp;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
	TDateTime N=Now();

	int Count=9999;

	PHONENUMBER *num=new PHONENUMBER[Count*Count];

	int TotalCount=0;

	for (int i = 1; i <= Count; i++) {
	for (int j = 1; j <= Count; j++) {
		num[TotalCount].f=i;
		num[TotalCount].r=j;
		TotalCount++;
	}
	}

	int shufflecount=10; //여기에 40만개를 넣으면 result에 40만개가 채워집니다.
	shuffle(num, shufflecount,TotalCount);

	PHONENUMBER *result=new PHONENUMBER[shufflecount];
	memcpy(result,&num[TotalCount-shufflecount],sizeof(PHONENUMBER)*shufflecount);


	for (int i = 0; i < shufflecount; i++) {
		Memo1->Lines->Add(result[i].GetNumber());
	}


	N=Now()-N;
	ShowMessage(N.FormatString("s.zzz"));
	delete[] num;
	delete[] result;

}
//---------------------------------------------------------------------------