Okay; “Hilf dir selbst, so hilft dir Gott”, as they say in Germany.
So I downloaded the source code from the Audex homepage (thanks for link!) and fixed it myself.
I found the fix in a thread on kde-apps.org:
Audex KDE-Apps.org
It turned out that the regular expression for scanning the Google response was wrong (don’t ask me what exactly was wrong; I’ve never been good at reading these expressions).
Here comes a quick HowTo, in case anybody wants to implement the fix, too:
o First, in order to compile the sources, I had to install the following packages:
cmake
gcc-c++
libkde4-devel
libkdcddb4-devel
libcompactdisc4-devel
cdparanoia-devel
o Download and extract the source code somewhere
o Follow the instructions on the Audex homepage, i.e.
In the source directory type:
mkdir build
cd build
cmake …
make
o At first, I got a compiler error for utils/hashlist.cpp: It did not find “close” and “lseek”.
Fixed this by adding “#include <unistd.h>”.
o Then, edit utils/coverfetcher.cpp according to the above mentioned thread, i.e. the code in method “parse_html_response” should read:
...
QRegExp rx("<a\\shref=\"(\\/imgres\\?imgurl=^\"]+)\">\\s\
]*<img^>]+src=\"(^>]+)\"></a>");
QString html = xml;
html.replace( QLatin1String("&"), QLatin1String("&") );
rx.setMinimal(TRUE);
int pos = 0; int i = 0;
while (((pos = rx.indexIn(html, pos)) != -1) && (i < fetch_no)) {
...
o Once more, type “make” in the build directory. You will find the new audex executable – now with a working cover fetcher – in the same directory.
o I did not perform “make install”, I just copied the new executable to /usr/bin/ thereby overwriting the “original” one.
Now everything works perfectly for me 
Have Fun!
Friedhelm.