Are you using Lr 1.4? and seeing these artifacts on photos which have either been downsized on export from Lr (like reduced for email or web posting)? There is a know fault in 1.4 which to my knowledge they never fixed which caused exactly what you're referring to... 2.5 doesn't seem to do it (I just finally upgraded), but there's an export plugin for Lr called
Lr/Mogrify which allows you to use Lr to export the full size image, and then uses imagmagick's tollbox to resize, sharpen and do whatever else you need - Until I upgraded, this plugin was the only way I would export other than full size images from Lr... check it out, it's good.
Google - lightroom 1.4 export artifacts - for more info and to determine if that's what you might be seeing.