It took a lot of effort but I actually found a working solution to my problem.
I first updated my phone to latest available Android version 2.3.6 and that did not solve my problem. So I installed an App that shows me more details about the network setup of my phone. And after some digging around I noticed what was wrong:
My phone didn't have a default IPv4 route.
How did that happen? In the DHCP I push a default route (dhcp option 3)!
I realized that when I just had the IPv6 link (which is part of a whole new internet connection) my phone DID connect to the internet with both IPv4 and IPv6. So I recreated the original setup and found that in that scenario indeed it does work. So what is different?
It took me two nights with wireshark to track the culprit down.
The real reason turns out to be that I have a static route for my DMZ which is pushed by my IPv4 DHCP server (dhcp option 121).
When I do that the Android phone only shows a route for the local subnet and the additional route I pushed. The default route is lost, hence IPv4 traffic is distorted. Apparently Android even no longer tries to do IPv4 DNS requests (which is the problem I started with).
All of my other systems (Windows {XP,7}, Linux, Android 3.x) do not do this and they keep all of the pushed routes and the default route.
Once I figured out what the problem was I could Google more effectively and I found this bug report: http://code.google.com/p/android/issues/detail?id=17525 Which in turn led to a workaround that actually works!!
Quote from http://forum.xda-developers.com/archive/index.php/t-635489.html
So as a "band aid fix it" i added the default gw to the static routes list... So the line in dnsmasq looks like: dhcp-option=121,<network>,<route>,0/0,192.168.1.254
So when looking at the DHCP ACK packet you'll see the default route in there twice: under option 3 and 121.
Quite an unexpected workaround ... but it works for me.
It turns out the Android behaviour is correct:
http://tools.ietf.org/html/rfc3442#page-5
"If the DHCP server returns both a Classless Static Routes option and a Router option, the DHCP client MUST ignore the Router option."