In the early 1990s, contemporary interstellar dust (ISD) penetrating deep into the heliosphere was identified with the in-situ dust detector on board the Ulysses spacecraft. Between 1992 and the end of 2007 Ulysses monitored the ISD stream. The interstellar grains act as tracers of the physical conditions in the local interstellar medium surrounding our solar system. Earlier analyses of the Ulysses ISD data measured between 1992 and 1998 implied the existence of big ISD grains [up to 10^-13kg]. The derived gas-to-dust-mass ratio was smaller than the one derived from astronomical observations, implying a concentration of ISD in the very local interstellar medium. We analyse the entire data set from 16 yr of Ulysses ISD measurements in interplanetary space. This paper concentrates on the overall mass distribution of ISD. An accompanying paper investigates time-variable phenomena in the Ulysses ISD data, and in a third paper we present the results from dynamical modelling of the ISD flow applied to Ulysses. We use the latest values for the interstellar hydrogen and helium densities, the interstellar helium flow speed of v_ISM,inf=23.2km/s, and the ratio of radiation pressure to gravity, beta, calculated for astronomical silicates. We find a gas-to-dust-mass ratio in the local interstellar cloud of R_g/d=193^+85_-57, and a dust density of 2.1+/-0.6x10^-24kg/m^3. For a higher inflow speed of 26km/s, the gas-to-dust-mass ratio is 20% higher, and, accordingly, the dust density is lower by the same amount. The gas-to-dust mass ratio derived from our new analysis is compatible with the value most recently determined from astronomical observations. We confirm earlier results that the very local interstellar medium contains big (i.e. 1 um-sized) ISD grains. We find a dust density in the local interstellar medium that is a factor of three lower than values implied by earlier analyses.