We present a detailed analysis of the evolution of the size distribution of fast-moving interstellar dust particles decelerating in a dusty plasma. The physical processes considered in this paper include sputtering by gas-grain collisions, and partial and complete evaporation, fragmentation, and cratering by grain-grain collisions. We find that the final distribution of grains, initially characterized by a power-law distribution in grain sizes, exhibits an excess of small-to-large particles, compared to the initial distribution. This excess depends on the initial grain velocity and should be detectable by infrared observations of low- and intermediate-velocity clouds with the Infrared Space Observatory scheduled for launch around 1996.