Silly question, are you sure the page in question ACTUALLY used table tags? A lot of dimwits out there are now abusing all sorts of other tags on TABULAR DATA, pretty much flushing semantics down the toilet and then having the nerve to call it more semantic. See the skins of several recent forum upgrades for examples of said stupidity in action. (vBulletin for example).
Also, what browser did you 'cut' from where it failed? All browsers are not created equal on this... the worst of the lot being drumroll..... IE. I know, no surprises there. Safari, FF and Chrome will auto-bold and center TH, while cut/paste from opera treats all elements as flat cells.
Also, only select the table, if you select 'extra' bits it can confuse Excel.
Try this small example table:
Which FF, Safari, Chrome and Opera all do a right fine job to Excel or LibreOffice -- while IE makes a right mess of it with a single column result in LibreOffice and one massive cell in Excel.
Excel can also just act... weird if you're using older versions (office 97)... or bleeding versions. (office 2010 on x64, it's fine on x32 for some reason) -- 2k3 and XP both handling it well... You may end up having to use libreoffice as a intermediary should you be on one of the versions that just completely screws up cut/paste.
Which is why increasingly I'm using LibreOffice instead of Office... even if the word processor still kerns text like a sweetly retarded rhesis monkey on crack. (It's not AS bad as it used to be when it was openOffice, at least on Windows (freetype is still USELESS for working with text) -- so glad there's a non-sun non-oracle fork now!)