I know of only one way that this can happen in windows, and has nothing to do with Steam other than their not-so-great decision to install all content into Program Files.
If you are on Windows 7 or Windows Vista, and you have UAC set to ON, then change it later to OFF, this can happen.
UAC does thing evil thing where if a program tries to write to a "protected" area like Program Files, EVEN IF YOU ARE ADMINISTRATOR, when you get a UAC prompt and give permission, it actually writes any files that would normally go into that directory into a "virtualized" directory somewhere else.
If you turn off UAC, that will no longer happen, and as an awesome bonus, it will no longer know about the files that it virtualized.
So in your case, if you had UAC on, installed a ton of games, then later got sick of UAC and turned it off, this would happen as you described.
See the second paragraph in "Features" in the article on User Account Control.
If you have done this and turn on UAC again, your content will come back, but be a TOTAL mess because if you've downloaded more stuff with UAC off, then that will be invisible when you turn UAC on, and vice versa.
this drove me a little crazy once before I realized what was happening.
i'm curious to know if this is your issue.
I had this problem before and I am not exactly sure which of these things fixed it but after doing them the problem stopped occurring.
- Verify Local Content via Steam. To do this right click the game on main menu, go to properties and then there is a button that says verify local content. (Actually one of my friend uninstalled then reinstalled prior to doing this)
- Never use the steam overlay for managing invites with Civ5.
- Defriend and retry then refriend and retry.
- Check your game version numbers match
I was basically trying everything I could think of then it started connecting without problems.
Best Answer
It seems a bug. If your game history, as suggested by @yx in comments, registered the matches as wins for your team, submit the bug to Dota 2 Beta dev forum. Copy down the IDs of your matches to let the devs check easier what went wrong.