They are from Nuln IMO.
Also, I think there's is some general misconception regarding the colours of Carroburg. According to the provinces descriptions, Carroburg lies in Middenland (and is politically part thereof) - If this is correct, I guess we can safely assume that the traditional colours for Carroburg were the same as Middenland (ie blue) - Only the Greatswords of Carroburg are known to distinctively wear black and red.
Checking back the description of Middenland makes things even more confusing as it indicates that Carroburg's original colour was white (probably because the city was occupied by Reikland then?) :
quote
the regiment fought until their white uniforms had turned red with the blood of their enemies. By tradition, from that day onward the Carroburg Greatswords have worn dark red uniforms.
end quote