I had a try with GDAL 2.4.0, released 2018/12/14 from OSGeo4W and then after update to GDAL 2.4.1, released 2019/03/15. I had no problem at all with your test data.

Result:

    gdalbuildvrt test.vrt *.tif
    0...10...20...30...40...50...60...70...80...90...100 - done.
    
    gdalinfo test.vrt|more
    Driver: VRT/Virtual Raster
    Files: test.vrt
           L333.tif
           L334.tif
    Size is 12000, 12000
    Coordinate System is:
    PROJCS["ETRS89 / TM35FIN(E,N)",
        GEOGCS["ETRS89",
            DATUM["European_Terrestrial_Reference_System_1989",
                SPHEROID["GRS 1980",6378137,298.257222101,
                    AUTHORITY["EPSG","7019"]],
                TOWGS84[0,0,0,0,0,0,0],
                AUTHORITY["EPSG","6258"]],
            PRIMEM["Greenwich",0,
                AUTHORITY["EPSG","8901"]],
            UNIT["degree",0.0174532925199433,
                AUTHORITY["EPSG","9122"]],
            AUTHORITY["EPSG","4258"]],
        PROJECTION["Transverse_Mercator"],
        PARAMETER["latitude_of_origin",0],
        PARAMETER["central_meridian",27],
        PARAMETER["scale_factor",0.9996],
        PARAMETER["false_easting",500000],
        PARAMETER["false_northing",0],
        UNIT["metre",1,
            AUTHORITY["EPSG","9001"]],
        AXIS["Easting",EAST],
        AXIS["Northing",NORTH],
        AUTHORITY["EPSG","3067"]]
    Origin = (260000.000000000029104,6714000.000000000931323)
    Pixel Size = (4.000000000000002,-4.000000000000001)
    Corner Coordinates:
    Upper Left  (  260000.000, 6714000.000) ( 22d37'48.79"E, 60d29'25.49"N)
    Lower Left  (  260000.000, 6666000.000) ( 22d41'14.15"E, 60d 3'38.39"N)
    Upper Right (  308000.000, 6714000.000) ( 23d30' 7.31"E, 60d30'58.14"N)
    Lower Right (  308000.000, 6666000.000) ( 23d32'51.92"E, 60d 5' 9.44"N)
    Center      (  284000.000, 6690000.000) ( 23d 5'30.54"E, 60d17'20.43"N)
    Band 1 Block=128x128 Type=Byte, ColorInterp=Palette
      Color Table (RGB with 256 entries)
        0: 0,0,0,255
        1: 52,52,48,255
        2: 64,48,24,255
    ...