So the OP went to the store to pick up some snacks, found a phone, person who lost phone remembered exactly where she lost phone, realized it wasn't there(and it did not occur to her upon not finding it that maybe she left it elsewhere), went to security, found someone in security, found a video over the exact spot where she lost phone, figured out exactly who it was who took the phone, went through surveillance to figure out that he left and where he went, grabbed two cops and found him in the parking lot?
That's the best 1AM surveillance crew ever assembled. EVER. And I'm not just talking about Wal-Mart.
Of course this time line is only believable if the OP and his GF are the slowest 1AM snack shoppers in the history of 1AM snack shoppers. (i.e. the OP was smoking at his car at 6AM outside of Wal-Mart)