Where do bad smells eventually go?
If you are smelling something, you are inhaling gases, particles, or a combination of the two.  They don't normally build up in the atmosphere because of three reasons:  transport/dilution (which you mentioned), chemistry, and deposition.  Yes there is plenty of fresh air out there but as you say, over billions of years there would be a lot of accumulation of odorous compounds if it weren't going somewhere.  Though, stinky air does get trapped near the ground sometimes during stagnation events, caused by a temperature inversion close to the surface which prevents mixing with the upper air.

Atmospheric chemistry usually involves the hydroxyl radical (OH) in some way.  Rapid chemical conversions of gases often depends on OH, which is cycling and replenished thanks to the abundance of oxygen and water vapor in the atmosphere.  Many gaseous pollutants will go through a series of chemical reactions with OH, other chemicals, and/or sunlight.  They are then converted to simpler chemicals that we don't really smell.  Most odorous pollutants are chemically converted quickly (e.g. hours, days).  Some pollutants do take years to convert (e.g. methane) and so accumulate in the atmosphere.  We don't smell them, though, because our ability to "smell" things is limited to organic compounds and other molecules like hydrogen sulfide and ammonia (see here). 

Deposition of air pollutants is dominated by precipitation, whereby rain can scavenge particles and chemically react with gases.  The rain deposits the pollutants (usually in a modified form) onto the surface of the Earth.  Dry deposition also occurs, especially with "sticky" compounds like ammonia.  However, dry deposition is not nearly as efficient as wet deposition.  Though, if particles are large enough, they will settle out of the atmosphere relatively quickly and deposit on the surface.

I suggest you read up a little on the topic here to get you more familiar with the different factors that affect air pollutants.