You have already answered yourself:

Quote Originally Posted by Mr Smith View Post
The first sentence (a) makes grammatical sense to me: The number is in the dative, and американцев is fine because nouns and adjectives that follow the words тысяча, миллион, миллиард and биллион are always in the genitive.
Yes, "тысяча" is grammatically a noun. When declining, "тысяча" declines but the subsequent noun always stays in genitive plural:

тысяча американцев, к тысяче американцев, тысячу американцев, без тысячи американцев, тысячей американцев, о тысяче американцев etc.

And yes, the same applies to higher numerals like миллион, миллиард etc.

Quote Originally Posted by Mr Smith View Post
The second sentence (b) seems to be inconsistent with the rule underlined above. Why is американцам dative? Why is it not genitive like in the first sentence?
That rule does not apply to the second sentence. As you see, in "трём тысячам трёмстам американцам" the noun does not follow any of "тысяча, миллион, миллиард". Here, "американцы" are attached to "триста" (300). The word "триста" is grammatically a numeral, not a noun. When a numeral like 300 is in nominative or accusative, it requires genitive plural of the noun:

пять американцев, десять американцев, сто американцев, триста американцев.

In cases other than nominative or accusative, both numeral and noun decline. It does not only apply to 300, but to all similar numerals:

к пяти американцам, к десяти американцам, к ста американцам, к трёмстам американцам;
без пяти американцев, без десяти американцев, без ста американцев, без трёхсот американцев;
пятью американцами, десятью американцами, ста американцами, тремястами американцами;
о пяти американцах, о десяти американцах, о ста американцах, о трёхстах американцах.

Please have in mind that in combined numerals, the last word matters.
The cases of 3000 and 3300 are different, because 3300 behaves the same way as 300.

Compare:
3000 - три тысячи американцев (dat: трём тысячам американцев)
3001 - три тысячи один американец (dat: трём тысячам одному американцу) - all numeral which end in 1 (except 11)
3002, 3003, 3004 - три тысячи два (три, четыре) американца (dat: трём тысячам двум/трём/четырём американцам) - all numeral which end in 2, 3, 4 (except 12, 13, 14)
3005, 3010, 3300 - три тысячи пять (десять, триста) американцев (dat: трём тысячам пяти/десяти/трёмстам американцам) - all numeral which end in 5, 6, 7, 8, 9, 0, and also 11, 12, 13, 14 ... 19.