I have never written a searchable audio player, but I suspect this is happening. Each audio packet is decoded into a fragment of the original sound wave. Usually these fragments successively rest against each other, and the result is a continuous wave, which you hear as sound without artifacts. When you search, you force two fragments from disparate parts of the file to rest against each other. This usually leads to a break in the resulting sound wave, which the ear perceives as a click or pop, or as you call it (I guess) an artifact.
Here is a more specific example. Suppose you played the first 25 audio packages before searching. Let's say packet 25 decodes into a wave whose last sample is 12345. While packet 25 is being transmitted to the speaker, you are trying to execute packet 66. Let them say that the first sample of packet 66 is 23456. Thus, the digital audio stream jumps from 12345 to -23456 through the search. This is a huge gap and will be heard as a pop.
I think one solution is to capture one additional packet, before you start searching (packet 26 in my example), decode it in a standalone buffer, apply fade out and then put it in the playback queue. After you try to find the right place, grab the first packet (66 in my eaxmple), decode it in another offline buffer, apply the attenuation, and then put it in the playback queue. This should provide smooth sound waves and search without artifacts.
If you are smart, you can make the fade in and fade out as short or as long as possible. I think that just a few milliseconds should be enough to prevent artifacts. You can even apply cross wilting with old and new packages. It can also be quite simple to mark the last value of the sample in the last packet before the search and gradually transfer it to zero for several samples, rather than immediately pull it to zero. This may be simpler than decoding an additional packet.
This is my guess on how to solve this problem. This is clearly a problem, so I recommend that you also watch the open source audio players and see how they implement the search. Good examples are programs like Audacity, Totem, Banshee, RhythmBox, Amarok, or VLC, or frameworks like GStreamer. If you find that they use well-known methods, please report a topic here. I think people will want to know what they are. Good luck