Here are some news as reply:

1. There have been some database errors which have been fixed (now all green). But it did not help with my issue.
2. The field has always been a date field, never changed. Also the freshly created field has always been a date field.

Now here is something:

Userlist Search Display is set to age => Search set to full age range => No results

Userlist Search Display set to date => Search set to full date range => Correct result shown (1 result)
Also in the latter the query shows that the date field is included.

So it seems that setting fields Userlist Search Display to age, the date fields get excluded from the query.

When I do a search on the demo page with default search range 0-100 then all members get shown. But only 4 have an age.
So it looks like it performs a "list all" rather than executing the age range.

Changing the age range to 1-100 shows only 4 members.

I have something similar now:

Created user age 20. Age is correctly shown as 20.
Allowed age range 18-25. So user is perfectly within the allowed rage.
Now go to search. Default value for age search is between 18 and 25.
Perform search, result: 0 user displayed. But it should be 1.
Change search range to 19-25
Perform search, result: 1 member displayed ( the user that has been created above)

So this seems that in this case a "list none" gets performed. I don't know why but maybe it correlates with the searchmode which is 1 in my case and seems to be 0 on the demo page.