Actually it's not a trademark, notice how it uses the (R) logo instead of the (TM) logo like on other products. It's restricted, referring to it being federally registered.
Uhh, as far as I understood it the (R) means that its a Registered Trademark, meaning registered and recognized with a federal office. Whereas the "TM" is used when a trademark application is currently in process or simply unregistered. In either case both the (R) and the TM are Trademarks.
Infact, "Microsoft" is also a (R)egistered trademark and carries the, (R).
Also, if you look at the logo for Windows 2000, you'll see the (R). This was well before the Lindows case.
http://media.gdgt.com/img/product/15/bqk/microsoft-windows-2000-oas-460.jpg
Looking through the US Trademark registery, it looks like Windows was registered in the mid 90's.. So if you look at a Windows 3.1 logo from 1992, it has the "TM" before it was (R)egistered.
http://onhax.files.wordpress.com/2009/12/win_three_point_one_onhax.gif
In terms of Microsoft vs Lindows, I can't find anything that says that Microsoft actually lost their trademark on Windows. However, I did find the settlement press release dated a few months after your reference.
http://www.microsoft.com/presspass/press/2004/jul04/07-19lindowspr.mspx
Now, if Microsoft did lose their trademark, someone might want to tell them, because they clearly call "Windows" a trademark in multiple locations. Here's one...
Do Not Use Microsoft Trademarks as Part of Your Product Name
Microsoft trademarks may not be incorporated as part of the name of another company's product or service. You may not include "
Windows," "Windows Media," or any potentially confusing variation in the name of your product or service. This same rule applies to other Microsoft trademarks, such as Microsoft, which should never be included in your product name or company name.
http://www.microsoft.com/about/legal/en/us/IntellectualProperty/Trademarks/Usage/WindowsMedia.aspx