A few strategies not already covered in the other answers come to mind:

# 1. Wham! Bam! Distraction!

We had a similar thing happen during one of our very first campaigns and I think our DM handled it elegantly.

We had a rogue who thought that being a thief, he had to be thieving the whole time, effectively draining energy from the group and the story. So we had to go talk to an NPC at their house and our thief wanted (again) to go around the back and break in. 
Instead of punishing him or telling him he couldn't, our DM made him find the magical chest we had been looking for in the woods behind the house. Since it could disappear randomly, the thief couldn't just let it lie and come back to it later. He couldn't call out to us without arousing suspicion from the NPC. And since the chest required two hands he couldn't take it with him while thieving.

So he ended up carrying/dragging the thing to the front of the house, making an excuse of having to go pee, getting lost in the woods and stumbling upon the thing (the home owner was sceptical but bought it).

In your case you could have Aleyd draw him close at the moment of the handshake and whisper a vital thing in their ear. Or just something like "Also, watch out for thieves around town. We hang a few every week but there's no end to them." Or have an explosion nearby. Or anything as long as it fits your story.

# 2. Play stupid games, win stupid prizes

Another strategy would be to have the theft be successful, but instead of gold there's iron nuggets in the purse. Aleyd is Captain of the Guard after all, of course she would have a decoy purse and keep her real purse in her inner pocket.

A stolen ring could look gold but turn out to be painted wood. A backpack could be full of painting supplies.

If this happens a few times, they'll soon learn petty theft isn't worth it and hopefully stop.

# 3. Boomerang

Similar to the second strategy, have the theft be successful. But as it turns out the purse was charmed with a spell that turns the owner bright blue for two hours if they don't have a piece of spruce (or a similar common but not easily obtainable object) tucked inside their pocket. The PC turns blue and is an easy target for the guards who know this happens to purse snatchers, unless of course they cover up with a sheet and act like an old diseased crone.

There's an infinite ammount of silly, harmless but inconvenient things you can come up with to dish out some instant punishment (e.g. a mute spell, a rash, total loss of bowel control to name a few).

----

I think the common thread here is: **don't let a thief hijack the story and wear out the rest of the party**. If you can't stop the thieving, at least make it useful and/or entertaining for the rest of the players.