[Kandorf]

Bueno, ya he hecho las funciones para ordenar correctamente, las posteo por si le resulta últil a alguien.
En realidad ordena un StringGrid dada una columna, pero vale con sustituir "Cells[Columna,i]" por "Cadenas[i]", suponiendo que el TStrings se llame Cadenas:

Código Delphi [-]
// Devuelve la longitud máxima de las cifras de un String
function FStrMaxLongitudCifra(Cadena: String): Integer;
var
  i, j: Integer;
  MaxLongitud: Integer;
begin
  MaxLongitud:=0;
  i:=1;
  while i<=Length(Cadena) do begin
    if (CompareStr(Cadena[i],IntToStr(0))>=0) and (CompareStr(Cadena[i],IntToStr(9))<=0) then begin
      j:=1;
      while (i+j<=Length(Cadena)) and (CompareStr(Cadena[i+j],IntToStr(0))>=0) and (CompareStr(Cadena[i+j],IntToStr(9))<=0) do
        Inc(j);
      if j>MaxLongitud then
        MaxLongitud:=j;
      i:=i+j;
    end else
      Inc(i);
  end;
  Result:=MaxLongitud;
end;

// Da a los números de una cadena la longitud especificada añadiendo 0s a los lados
function FStrAgrandarNúmeros(Cadena: String; Longitud: Integer): String;
var
  i, j: Integer;
begin
  if Longitud>0 then begin
    if Longitud>=3 then
      Longitud:=Longitud;
    i:=1;
    while i<=Length(Cadena) do begin
      if (CompareStr(Cadena[i],IntToStr(0))>=0) and (CompareStr(Cadena[i],IntToStr(9))<=0) then begin
        j:=1;
        while (i+j<=Length(Cadena)) and (CompareStr(Cadena[i+j],IntToStr(0))>=0) and (CompareStr(Cadena[i+j],IntToStr(9))<=0) do
          Inc(j);
        Cadena:=Copy(Cadena,0,i-1)+DupeString('0',Longitud-j)+Copy(Cadena,i,Length(Cadena));
        i:=i+Longitud;
      end else
        Inc(i);
    end;
  end;
  Result:=Cadena;
end;

// Ordena un StringGrid dado una columna que puede contener Letras y Números
procedure FStgOrdenarLN(Grid : TStringGrid; Columna:integer);
var
   i, j: Integer;
   Temp: TStringList;
   AuxCadena1, AuxCadena2: String;
   Longitud1, MaxLongitudNúmero: Integer;
begin
  Temp:=TStringList.Create;
  with Grid do begin
    for i:=FixedRows to RowCount-2 do begin
      // Las dos siguientes líneas las hago fuera en un intento de reducir el número de llamadas a las funciones, más abajo se repiten otra vez
      AuxCadena1:=Cells[Columna,i];
      Longitud1:=FStrMaxLongitudCifra(AuxCadena1);
      for j:=i+1 to rowcount-1 do begin
        AuxCadena2:=Cells[Columna,j];
        MaxLongitudNúmero:=FStrMaxLongitudCifra(AuxCadena2);
        if Longitud1>MaxLongitudNúmero then
          MaxLongitudNúmero:=Longitud1;
        if AnsiCompareText(FStrAgrandarNúmeros(AuxCadena1,MaxLongitudNúmero),FStrAgrandarNúmeros(AuxCadena2,Max  LongitudNúmero))>0 then begin
          Temp.assign(rows[j]);
          rows[j].assign(rows[i]);
          rows[i].assign(Temp);
          // Aquí repito las funciones mencionadas anteriormente, ya que la Cadena de referencia cambia
          AuxCadena1:=Cells[Columna,i];
          Longitud1:=FStrMaxLongitudCifra(AuxCadena1);
        end;
      end;
    end;
  end;
  temp.free;
end;

Espero que resulte útil a alguien.

Por favor, opinen, el tiempo de proceso aumenta y se nota, yo estoy ordenando actualmente 625 cadenas bastante largas.
Estaría encantado de que me corrigiérais la función

Saludos.