We present a novel approach to constrain the formation channels of ultra-compact dwarf galaxies (UCDs). They most probably are an inhomogeneous class of objects, composed of remnants of tidally stripped dwarf elliptical galaxies and star clusters that occupy the high mass end of the globular cluster luminosity function. We use three methods to unravel their nature: 1) we analyzed their surface brightness profiles; 2) we carried out a direct search for tidal features around UCDs; and 3) we compared the spatial distribution of GCs and UCDs in the halo of their host galaxy. Based on FORS2 observations under excellent seeing conditions, we studied the detailed structural composition of a large sample of 97 UCDs in the halo of NGC1399, the central galaxy of the Fornax cluster, by analyzing their surface brightness profiles. We found that 13 of the UCDs were resolved above the resolution limit of 23pc and we derived their structural parameters fitting a single Sersic function. When decomposing their profiles into composite King and Sersic profiles, we find evidence for faint stellar envelopes at {mu}=~26mag/arcsec^2^, surrounding the UCDs up to an extension of 90pc in radius. We also show new evidence for faint asymmetric structures and tidal tail-like features surrounding several of these UCDs, a possible tracer of their origin and assembly history within their host galaxy halos. In particular, we present evidence for the first discovery of a significant tidal tail with an extension of ~350pc around UCD-FORS2. Finally, we studied the local overdensities in the spatial distribution of globular clusters within the halo of NGC1399 out to 110kpc to see if they are related to the positions of the UCDs. We found a local overabundance of globular clusters on a scale of <=1kpc around UCDs, when we compared it to the distribution of globulars from the host galaxy. This effect is strongest for the metal-poor blue GCs. We discuss how likely it is that these clustered globulars were originally associated with the UCD, either as globular cluster systems of a nucleated dwarf galaxy that was stripped down to its nucleus, or as a surviving member of a merged super star cluster complex.