We report the discovery of the millisecond pulsar (MSP) PSR J1950+2414 (P = 4.3 ms) in a binary system with an eccentric (e = 0.08) 22 day orbit in Pulsar Arecibo L-band Feed Array survey observations with the Arecibo telescope. Its companion star has a median mass of 0.3M(circle dot) and is most likely a white dwarf (WD). Fully recycled MSPs like this one are thought to be old neutron stars spun-up by mass transfer from a companion star. This process should circularize the orbit, as is observed for the vast majority of binary MSPs, which predominantly have orbital eccentricities e <0.001. However, four recently discovered binary MSPs have orbits with 0. 027 <e <0.44; PSR J1950+2414 is the fifth such system to be discovered. The upper limits for its intrinsic spin period derivative and inferred surface magnetic field strength are comparable to those of the general MSP population. The large eccentricities are incompatible with the predictions of the standard recycling scenario: something unusual happened during their evolution. Proposed scenarios are (a) initial evolution of the pulsar in a triple system which became dynamically unstable, (b) origin in an exchange encounter in an environment with high stellar density, (c) rotationally delayed accretion-induced collapse of a super-Chandrasekhar WD, and (d) dynamical interaction of the binary with a circumbinary disk. We compare the properties of all five known eccentric MSPs with the predictions of these formation channels. Future measurements of the masses and proper motion might allow us to firmly exclude some of the proposed formation scenarios.