Yes, this is a weird duck. Quack. Quack.
If I play further with this, I am tempted to see if char* str[]; is a valid syntax or not - having the blank dimension would certainly be nice as a "heads up". But yeah, from the OP's code, he expects the dynamic array to extend past the "starter header" as a continuation of the single element defined in the structure.

Some OP code:

for (index = 0; index <= count; index++) {
        tmp = *av_fetch(val_arr,index,0);
        string = SvPVutf8(tmp,len);
        message->str[index] = savepvn(string,len);
}
[download]

Of course since the whole purpose of XS is to write C code, something like this would be more appropriate (untested):

int n = count;
char* p = &m.str;
while (n--)
{
  ....blah...
  *p++ = savepvn(string,len);
}
[download]

Using an index is a mess because this often will result in code that calculates index*sizeOfelement+arrayBase to get to the address. Having a pointer eliminates this calculation. Incrementing the pointer (p++) by sizeOfelement is very fast because that is a constant which is actually part of the machine instruction (not some number that is read from data memory). This instruction is typically called something like "add immediate to register". while (n--) runs very fast because there are special op codes that increment or decrement by one (this is much faster than incrementing the pointer because the instruction is shorter). There are also special op codes that check for zero or non-zero.

So far, I've learned some things that were new to me about XS. So this has been interesting. However, it is not at all clear that besides being a good intellectual exercise that this will result achieving a significant end goal. This is a lot of complication to make a clone of a Perl Array of Strings in a different format. For all I know, it could be "good enough" to leave the Perl data structures "as is" and write good C code to access the data for the intended but as of yet unstated purpose/application.

To proceed any further, we'd need to know more about what this is being used for.
Cheers,
Marshall