A search for stable and long-lived massive particles of electric charge |Q/e|=1 or fractional charges of 2/3, 4/3, and 5/3 is reported using data collected by the OPAL detector at LEP, at centre-of-mass energies from 130 to 209 GeV. These particles are assumed to be pair-produced in e+e- collisions and not to interact strongly. No evidence for the production of these particles was observed. Model-independent upper limits on the production cross-section between 0.005 and 0.028 pb have been derived for scalar and spin-1/2 particles with charge +-1. Within the framework of the Constrained Minimal Supersymmetric Standard Model (CMSSM), this implies a lower limit of 98.0 (98.5) GeV on the mass of long-lived right (left)- handed scalar muons and scalar taus. Long-lived charged heavy leptons and charginos are excluded for masses below 102.0 GeV. For particles with fractional charge +-2/3, +-4/3 and +-5/3, the upper limit on the production cross-section varies between 0.005 and 0.020 pb. All mass and cross-section limits are derived at the 95% confidence level and are valid for particles with lifetimes longer than 10^-6 s.