Shiraz' advice is all valid for local (not AD) Windows accounts, but I believe the threat you're raising isn't related to the SAM-stored local Windows passwords, since you're talking about an Active Directory setup with Windows systems joined to the domain.
Presumably the message security/windows credentials only allows access to the user accounts you've setup in Active Directory. [All discussion here assumes we're talking about those AD accounts, not local accounts on each Windows client.]
Assuming you've only allowed access to the WCF service for AD accounts, then the WCF service is only practically vulnerable to attackers who can retrieve (or guess) the plaintext password. Since you raised the spectre of live CD attacks, I'll further assume you're only worried about attacks on the Windows clients and not on the AD domain controller (whose physical security is presumably much stronger than the physical protections of the Windows clients).
So the threat you're raising is the possibility that an attacker could somehow find the user's AD password somewhere on the hard drive of the Windows client (or an easily-broken equivalent of their password). That is not the kind of attack for which the Live CDs are generally useful - as Shiraz indicated, they're good for digging up the password hashes out of the local SAM and helping to brute-force try many password combinations (or compare them to a local or online "rainbow table" that contains a ton of pre-calculated password values). Some of these tools also scan through local caches of such passwords, such as older browsers that saved your password for web site authentication - though modern browsers pretty much all have avoided those plaintext backdoors now.
The main cache of a user's AD password on a Windows client is the "cached domain credentials" (which allows you to logon with your domain password even if you're not connected to the network). This isn't stored as just a simple hash of your AD password - instead, it's doubly-hashed and encrypted with the local SYSKEY, making it an order of magnitude more time-consuming to try to brute force. A reasonably long or strong (or both) AD password makes brute-force attacks pretty much infeasible except for very dedicated attackers (like espionage, governments, etc.) So your most effective tool to make sure this is infeasible is to set a reasonable password policy - complex characters and a decent minimum length is fine; non-complex but very long passwords (aka passphrases) are also worthwhile.
Other caches of the password might exist, but that's dependent entirely on whether your users are using really crappy applications - there are fewer and fewer such applications on the market today, but never say never.