I have had this issue as well using my 9.3.1 server. I am waiting for the install of our 10 server now as I assume this will solve the problem.
Dasa, is there anything special that needs to be in the map or feature class before a feature class is published to allow it to work as type feature? In my application I have very strange results. For example, I can use ....mapserver/11, but not ...mapserver/12. I can always get my point layer, but only one of my line layers works correctly. I was thinking that maybe on the 9.3.1 server I needed to set something up before hand. I have cleared cache, restarted, republished, tried our main server and our test server, many different map services and I cannot get consistent results. If I use the same layers in a query widget the query always works and If I make the layer type dynamic it will work as well(for display).