I'm not sure about "lowest possible speed".
I generally burn at a good deal less than full speed, but I've read somewhere that modern x52 or x48 CDs don't perform well if you burn then at x1, for example. The same principle may apply to DVDs.

Also, while cleaning the lens is worth a try, the lasers in DVD/CD burners do wear out after many hours of use (especially burning) and eventually replacement is the only option.