This answer has been deleted for the first time, so this is a re-post. The first answer also had an error in the plot. Since the questioner asked the following question "Is there a general solution strategy to equations of this kind?" I'll try to respond.
The half-iterate of a function can be found by expressing its superfunction in a form of Newton series:
$$f^{[1/2]}(x)=\sum_{m=0}^{\infty} \binom {1/2}m \sum_{k=0}^m\binom mk(-1)^{m-k}f^{[k]}(x)$$
Where $f^{[k]}(x)$ means k-th iterate of $f(x)$ This series converges if two criteria are met:
The superfunction of f(x) grows slower than factorial
Runge phenomenon does not appear.
There is a number of strategies to combat Runge phenomenon which are outside of this answer's scope. It is worth noting though that trying to find a half iterate of the function $f(x)=\cos x$ leads to this Runge swamp and one needs to employ one of the mentioned techniques to acheve convergence.
Opposite case is with the function $f(x)=\sin x$. The superfunction is limited by $\pm 1$ and the series converges without any problem.
Below is a plot of half-iterate of $\sin x$, obtained with this formula. It is periodic with the same period as $\sin x$. The blue curve is the half-iterate, and the red curve is the half-iterate, repeated twice, and we can see that it is indeed very similar to sine function.
alt text http://storage5.static.itmages.ru/i/11/0727/h_1311791301_fc8c78d2ec.png
This plot is made from the first 20 terms of the above series.
This formula for the half-iterate can be used to find not only half-itertes but any real (or even complex!) iterate of a function by substituting the needed value instead of 1/2.
The formula can be also written in the following forms:
$$f^{[s]}(x)=\lim_{n\to\infty}\binom sn\sum_{k=0}^n\frac{s-n}{s-k}\binom nk(-1)^{n-k}f^{[k]}(x)$$
$$f^{[s]}(x)=\lim_{n\to\infty}\frac{\sum_{k=0}^{n} \frac{(-1)^k f^{[k]}(x)}{(s-k)k!(n-k)!}}{\sum_{k=0}^{n} \frac{(-1)^k }{(s-k) k!(n-k)!}}$$
There are also some other formulas giving the same result.