What's the number of decibinary numbers that evaluate to given decimal number?

You can use generating functions for this. The generating function for decibinary numbers is

\begin{eqnarray} \prod_{k=0}^\infty\sum_{j=0}^9x^{2^kj}=\prod_{k=0}^\infty\frac{1-x^{10\cdot2^k}}{1-x^{2^k}}\;. \end{eqnarray}

The number of ways to represent $n$ as a decibinary number is the coefficient of $x^n$ in this generating function. For instance, for decibinary numbers with up to $4$ digits, we can truncate the product at $k=3$ and let Wolfram|Alpha compute the expansion:

$$ 1 + x + 2 x^2 + 2 x^3 + 4 x^4 + 4 x^5 + 6 x^6 + 6 x^7 + 10 x^8 + 10 x^9 + 13 x^{10} + \cdots\;,$$

in agreement with your counts.

Indeed, you need more than just the number of representations for a given number $n$. Here is a way to compute the table.

Let $N(d, m)$ be the number of decibinary representations of length $m$ or less decibits of the decimal value $d$. To find $N(d, m+1)$ you need to find out what are the possible values of the $m+1$-th (leading) decibit and sum up the number of possible representations starting with those digits. To achieve that, observe that the number of representations with leading digit $d_{m+1}$ is actually the number of representations of the remainder $d - d_{m+1}\cdot{}2^{m}$ with $m$ decibits, so

$$N(d, m+1) = \sum_{p=0}^{p_{\textrm{max}}}N(d-p\cdot{}2^{m}, m)$$

where $p_\textrm{max} = \min(9, \left\lfloor\frac{d}{2^m}\right\rfloor)$. Allowing $p$ to start from $0$ effectively means that $0001$ is counted as a valid 4-digit decibinary representation of $1$. This is important for the last part.

The number of 1-decibit representations is easy:

$$N(d, 1) = \begin{cases}1, \mbox{if } d < 10\\0, \mbox{otherwise}\end{cases}$$

Computing $N$ is a typical dynamic programming problem. You fill up $N(d, m)$ by iterating $d$ from $0$ to some max value $d_\textrm{max}$ and $m$ from $1$ to $\lceil\log_2{}d_\textrm{max}\rceil$. The longest representation is always the one using $0$ and $1$ only, i.e., the binary one, and its length is a monotonic function of $d$.

Finally, $f(n) = N(n, \lceil\log_2{}d_\textrm{max}\rceil)$. The space complexity of the algorithm is $O(d \log d)$. For the test cases (limited to the first $10^7$ table entries), $d_\textrm{max} = 4449$ and the table has $57850$ entries.