Ahhh, bloody heck. One minute after posting the question, Rubber Duck Debugging rescues me again.

In Inline::C, it explains the Inline_Stack_Reset call:

use warnings;
use strict;

use Inline 'C';

my @random_numbers = getRand(1, 1000, 100);

print "$_\n" for @random_numbers;

__END__
__C__

#include <stdlib.h>

void getRand (int start, int end, int iterations){

    time_t t;
    srand((unsigned) time(&t));

    inline_stack_vars;
    inline_stack_reset;    // <-- HERE

    int i;

    for (i = 0; i < iterations; i++){
        int randomNum = rand() % (end - start);
        inline_stack_push(sv_2mortal(newSViv(randomNum)));
    }

    inline_stack_done;
}
[download]

That resolves the problem. Effectively, it resets the stack before appending to it.