Martin,
Good news is I reproduced the problem. I also spent some time searching the Internet for the answer (I suppose you have done that too). I found lots of pages warning that "immediate" update isn't the same thing as instantaneous.
Bad news is I haven't found a work around. Since this problem is not specific to the data service, please consider posting a question to the Notes & Domino forum here:
http://www-10.lotus.com/ldd/ndseforum.nsf
Or you can raise the question through other support channels.
Sorry I don't have a better answer, but please let me know what you find. If all else fails I suppose we could consider a future enhancement to the data service. For example, we could add a URL parameter to trigger an immediate FT index update.
Thanks.
-- Dave