This question is quite a common one for those first learning about capacitors.
First, let's remember that an electric field caused by stationary charges is conservative--this can easily be explained since a single charge creates a conservative field, and superposition of two conservative fields creates another conservative field.
So, the field generated by a floating capacitor has to be conservative. The universe isn't crazy, so it's probably us missing something? Are there any assumptions that we made while calculating the field? Yes, there are:
We assumed that the capacitor was infinite in size, and thus the field became uniform.
But, here, we are dealing with the edges of the capacitor. The field is not uniform here, it is more like (second half of image):

or:

When it comes back out, the x-component of the field will be against the velocity of the particle, slowing it down back to the initial speed.
For example, for a positively charged particle, the trajectory is as follows:

The green indicates the force on the particle at various points. Once the particle exits, it is "pulled back". The net effect is that the speed stays the same but the direction does not. Perfectly in accordance with conservation of energy.
Ignoring fringe fields can lead to some interesting apparent paradoxi, like the origin of the force that pulls a dipole slab into a capacitor.