TFS 2010 and Visual Studio 2008 - Gated Checkins not working

This is an infuriating issue which took me a while to track down, so I'm posting here in hope that it is useful for someone someday:

Issue:

Gated Checkin works fine from Visual Studio 2010, however from Visual Studio 2008 with the Forward Compatibility Pack it always turns into a Continuous Integration build.

Solution:

Delete the Clean Build checkin policy which ensures that you can't check-in if the previous build failed. It looks like a bug as you can have this check-in policy and Gated Checkins in Visual Studio 2010