If in fact the evidence has been lost, it would be very difficult for them to establish a CCW-type charge against you; it may not be possible. But I am skeptical that the evidence has in fact been lost.
If you have a lawyer for a CCW charge in Oklahoma, have your lawyer obtain a copy of the police report from the traffic stop. It likely specifies what evidence was seized.

