I'm not sure what your "could be removed" string in the output is supposed to denote, but assuming that output string could be removed, the following may provide some ideas:

use strict;
use warnings;

my @cleared = (
    'JOB::HEREISASTRING', 'Something',
    'StringA',            'StringB',
    'StringC',            'StringD',
    'Something Else',     'StringE',
    'StringF',            'StringG',
    'StringH ',           'JOB::HEREISANOTHERSTRING',
    'Something',          'StringI',
    'StringJ',            'StringK',
    'StringL',            'Something Else',
    'StringM',            'StringN',
    'StringO',            'StringP ',
);

my @result;
my $prefix = '~~Something~~';

foreach my $x (@cleared) {
    if ($x =~ /JOB::(.*)/) {
        $prefix = "";
    }
    elsif ($x =~ m/^Something Else/) {
        $prefix = "~~Something Else~~";
    }
    elsif ($x =~ m/^Something/) {
        $prefix = "~~Something~~";
    }

    print "$prefix$x\n";
}
[download]

Prints:

JOB::HEREISASTRING
~~Something~~Something
~~Something~~StringA
~~Something~~StringB
~~Something~~StringC
~~Something~~StringD
~~Something Else~~Something Else
~~Something Else~~StringE
~~Something Else~~StringF
~~Something Else~~StringG
~~Something Else~~StringH 
JOB::HEREISANOTHERSTRING
~~Something~~Something
~~Something~~StringI
~~Something~~StringJ
~~Something~~StringK
~~Something~~StringL
~~Something Else~~Something Else
~~Something Else~~StringM
~~Something Else~~StringN
~~Something Else~~StringO
~~Something Else~~StringP
[download]

The trick is to use a "state" variable (in this case $prefix) to remember what state the parser is in. This is a trivial case of a state machine which can be used to simplify implementing many parsing and processing systems.