I think everyone knows useful algorithms with constant complexity, e.g. test if a number is even by checking the last bit, or negative by checking the sign bit. You might need to argue for a random access model to the input if you can't guarantee you see the start or end of the stream first (big/little endian issues) but still one of these is valid and used all the time. That is not strictly decreasing but it does, as asked, solve a useful problem with a subset of the input.
But there are many reasonable algorithms with such features. Take a Monte Carlo algorithm that learns how much white space is in a document. It can sample less and less of a larger document and still have reasonable statistics. Polling data is this way too.
Also consider machine learning. When I worked on natural language recognition years back we found you don't keep training on equal proprotions of data, you can reduce the amount you sample as you get a larger corpus to study. I'd call that a form of "decreasing".
I think the main issue is as Raphael mentioned the word "complexity" which invites a purely asymptotic tone. If so you ignore any changes in behavior before some constant size $B$. And so to be a decreasing function from that point on would be hard to do meaningfully. But what about a function like $O(n^{1/n})$, doesn't that have some meaningfully "decreasing" complexity without being a strictly decreasing function?
I would argue that decreasing has a natural interpretation that is meaningful, e.g. that an algoirthm in some initial range behaves quadratically, but in large enough inputs can become linear.
A real life example of what I mean is matrix multiplication. The complexity by Coppersmith-Winograd is around $O(n^{2.3})$ but it takes a very large $n$ to get to that complexity. So in reality we model it something like $O(n^3)$ for $n<100$, swapping to $O(n^{2.7})$ for some regime $100\leq n\leq 1,000,000$, and perhaps some other complexities after that all the way until we hit the extreme regime. (Yes experts, those ranges are hypothetical for illustration, not the result of citing some specific test suit!)
That I would argue is a form of "decreasing" complexity and found quite often in useful algorithms.