you really seem to be experiencing weird issues...
I don't really see a possibility how WP-Table Reloaded could have issues with caching. All it does is print something on the page (the table HTML), adds a few CSS/JS commands and offers some static JS files to download. So nothing really that is dynamic and can not be cached. (Are static JS files actually cached by WP-Supercache?)
And no, I do not use any caching plugin.
I don't get any errors in Firefox nor IE 8. However, I get an error in the TableTools.js with IE 8 and Compatibility Mode on (I don't have an IE 7 to test, but it should be the same error). That particular issue is probably caused by the minify that I did with that JS file (I'll have to check again with the unmodified version).
But that issue only affects the TableTools extension. There is never a problem with the sorting or searching however.
So, while it is really odd, unfortunately I don't know what might be causing it. :-( It could be a bug in the DataTables library, or maybe a conflict with another JS script.
Can you provide the URL of the page with the table?