Maybe you get your hands on a 2 Disc French Edition to speed it up.

First of al there is some Bonus on it, which are not in other PAL releases, second the french Companies are sometimes very lucky in quality. (Its no guarantee, but a try.)

You should never try a german release.. you have to be really lucky if a german release of such an old movie is in quite good shape...

http://www.amazon.fr/African-Queen-%C3%89dition-Collector-DVD/dp/B000096J3U/ref=sr_1_1?ie=UTF8&s=dvd&qid=1223798064&sr=1-1

There is also a Hong Kong release:

http://www.yesasia.com/global/the-african-queen-hong-kong-version/1004253119-0-0-0-en/info.html

And a japanese release:

http://www.yesasia.com/global/sekai-misaku-eiga-zenshu-90-the-african-queen-japan-version/1004146969-0-0-0-en/info.html

(Yesasia is known for NOT SELLING BOOTLEGS.. so it should be a official release..)