There is a flaw in your very approach: You have a public function returning a ForwardDecl instance, so every client wanting to use this function also must include the according definition of that type, which implies you can make that type public from the beginning. This includes making the function definition inline, which will fix your linker problems.
However, if you really want to hide the content of that structure and you are sure clients don't need it directly, you can declare it and then pass around references to such a structure (or pointers, but raw pointers are evil albeit not in the same league of evil as #macros). In that case, I would still make the function definition inline.
If you really, really want to not make the function inline, you can also explicitly instantiate the function template for the types that you need. You would add at the end of the template's .cpp file something like template class Interface<int>;
(I don't remember the exact syntax so take that with a few flakes of fleur de sel, check out the C++ FAQ at parashift.com for more info). This makes the template a little less universal though, as it requires adjustments for any type that you want to use it with, but it can be an approach in some corner cases.