Ultra-compact dwarf galaxies (UCDs) were serendipitously discovered by spectroscopic surveys in the Fornax cluster 20 yr ago. Nowadays, it is commonly accepted that many bright UCDs are the nuclei of galaxies that have been stripped. However, this conclusion might be driven by biased samples of UCDs in high-density environments, on which most searches are based. With the deep optical images of the Fornax Deep Survey, combined with public near-infrared data, we revisit the UCD population of the Fornax cluster and search for UCD candidates, for the first time, systematically out to the virial radius of the galaxy cluster. Our search is complete down to magnitude m(g) = 21 mag or M-g similar to -10.5mag at the distance of the Fornax cluster. The UCD candidates are identified and separated from foreground stars and background galaxies by their optical and near-infrared colours. This primarily utilizes the u-i/i-Ks diagram and a machine learning technique is employed to incorporate other colour combinations to reduce the number of contaminants. The newly identified candidates (44) in addition to the spectroscopically confirmed UCDs (61), increase the number of known Fornax UCD considerably (105). Almost all of the new UCD candidates are located outside the Fornax cluster core (360 kpc), where all of the known UCDs were found. The distribution of UCDs within the Fornax cluster shows that a population of UCDs may form in low-density environments. This most likely challenges the current models of UCD formation.