If you are going to pass around complex objects, you might find it nessesary to use XS, but maybe Inline::CPP is smart enough to get it to work. Try inline first, it shouldn't take long to test, and you can always convert to XS later.

XS is more low-level, meaning it requires you to "spell out" more of the C/Perl-interface code, but it also gives you the most flexibility. Swig is like XS but language-independant (and from what I heard, slightly easier than XS) but I haven't used it at all. Both Swig and Inline::C(PP) produce XS code, by the way.

It's possible to use the same XS code in win32 and unix; it should be slightly easier than writing portable C, since you're linking against perl, which provides a lot of platform-independent routines. See perlapi, for instance.