C++ – Solving the Visual Studio 2010 AlwaysCreate rebuild issue

I've a C++ project that I'm currently porting from VS2008 to VS2010. When I build the project, Visual Studio 2010 reports the build as successful but if I then press F5 to start the debugger I'm told that the project is not up to date. If I ignore this warning, I can continue debugging ok, but if I press ok, the whole project (many hundreds of source files), gets rebuilt from scratch. The output contains the following;

1>------ Build started: Project: SCCW-VC2010, Configuration: Debug Win32 ------
1>Build started 15/11/2010 14:47:40.
1>InitializeBuildStatus:
1>  Creating "Debug\SCCW-VC2010.unsuccessfulbuild" because "AlwaysCreate" was specified.
1>Midl:
1>  All outputs are up-to-date.
1>ClCompile:
1>  tinedit.cpp
1>  _WIN32_WINNT not defined. Defaulting to _WIN32_WINNT_MAXVER (see WinSDKVer.h)
1>  Automatically linking with sfl504d.lib
1>  Automatically linking with ot1104d.lib
1>c:\program files\rogue wave\stingray studio 10.4\include\toolkit\sectndlg.h(134): warning C4996: 'strcpy': This function or variable may be unsafe. Consider using strcpy_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.
1>          c:\program files\microsoft visual studio 10.0\vc\include\string.h(105) : see declaration of 'strcpy'
1>  Automatically linking with og1204d.lib
1>  Automatically linking with RWUXThemeD10.lib
1>  profile.cpp
1>  ZOffsetDialog.cpp

Half an hour later, once the build is finished, the debugger starts. My guess is that the message

Creating "Debug\SCCW-VC2010.unsuccessfulbuild" because "AlwaysCreate" was specified.

is part of the problem, but I cant tie this to a project setting. I've found some help on google, but nothing that has worked thus far. Anyone else had this problem and know of a fix?

Edit: As per Jalf's suggestion in the comments below, I have created a new projected, imported all my files into that project, and the new project has the same problems. Specifically, I copied over all the following groups;

<ClCompile Include="..\MyDir\MyFile.cpp"/>
<ClInclude Include="..\MyDir\MyFile.h" />
<None Include="res\MyFile.ico" />  (and all similar resources)
<Library Include="..\MyDir\MyFile.lib" />

Edit2: After going through all the header includes I eventually found 3 that did not exist. Removing them and doing a rebuild all on the original project seems to have fixed the problem. Some of the blog posts that mention this problem refer to it as a bug, and two days of lost time later, I tend to agree. Thanks for the answers and comments provided.

Edit3: And one day later the problem is back! Making any edit to any file in the project once again causes a full rebuild. As per John Dibling's answer, the project does include some static libraries, including Stingray. I'm ditching VS2010 and moving back to VS2008, as I have deadlines. For related information, see the following links;

VS2010 always thinks project is out of date but nothing has changed

http://social.msdn.microsoft.com/Forums/en-US/vcgeneral/thread/38c08137-3bb0-4143-b97f-72d077646318

http://blogs.msdn.com/b/vsproject/archive/2009/07/21/enable-c-project-system-logging.aspx

Final Edit The release of VS2010 SP1 has solved this problem, and builds are now fast and efficient.