Firstly, that's got nothing to do with FF's use of getElementById, it's because first time FF calls that function the style is not stored on the element, it's in a style attribute, which for some reason it treats differently. Where you have:
[code]col = blue;[/col]
Then your original IE code should work on FF too. Or, better yet, do:
document.getElementById('table').style.borderColor = 'blue'
Saves a lot of time in subsequent uses if you use that variable instead.
var elStyle = document.getElementById('table').style;
elStyle.borderColor = 'blue';