First, we have InterlockedExchange64();
http://msdn.microsoft.com/en-us/library/windows/desktop/ms683593%28v=vs.85%29.aspx
LONGLONG __cdecl InterlockedExchange64( __inout LONGLONG volatile *Target, __in LONGLONG Value );
Second, we have the compiler intrinsic, _InterlockedExchange64(), note the absence of volatile;
http://msdn.microsoft.com/en-us/library/1s26w950%28v=vs.80%29.aspx
__int64 _InterlockedExchange64( __int64 * Target, __int64 Value );
Next, we have InterlockedExchangePointer() which like InterlockedExchange64(), uses volatile.
http://msdn.microsoft.com/en-us/library/windows/desktop/ms683609%28v=vs.85%29.aspx
PVOID __cdecl InterlockedExchangePointer( __inout PVOID volatile *Target, __in PVOID Value );
But now we come to the intrinsic for pointer exchange, _InterlockedExchangePointer() and here we see volatile used!
http://msdn.microsoft.com/en-us/library/853x471w.aspx
void * _InterlockedExchangePointer( void * volatile * Target, void * Value );
The underlying instruction is the same in all cases, so what gives? documentation error?
The GCC instrincs don't mention volatile for exchange, but then they don't mention it for CAS either! so that doesn't help.
My view is that a CAS target is volatile, because you can only know at run time if the exchange will occur; but atomic exchange should not be volatile, because the target is always updated (even if it's value doesn't change), so the compiler has no uncertainty.
I see also the function for InterlockedIncrement() are volatile, but the instrincs are not. The intrinsics for CAS have volatile for their destinations.
MSDN is riddled with mostly minor documentation errors (for instance, __readfsdword was marked as kernel only under the VS 2005 docs), what you should really pay attention to is the definition the compiler uses, in this case, the definitions in intrin.h (taken from VS2010 Ultimate SP1):
__MACHINEI(long _InterlockedExchange(long volatile *, long))
__MACHINEIA64(__int64 _InterlockedExchange64(__int64 volatile *, __int64))
as we can see they are indeed volatile pointers that are required.
One final thing to note, all your links are the VS 2005 docs (default linked to by google for older intrinsics), so make sure you use the drop down at the top of the page to switch to the latest versions.