19
I struggled with the same question on a recent project of mine where I wanted to talk to Trello and Salesforce in pure VBA without installing any plugins, opening up Visual Studio, or other hacks. Ended up writing my own library (based heavily on one of my favorites, RestSharp).
Warning, shameless plug: https://github.com/VBA-tools/VBA-Web
Some fun features include Mac support(!), authentication (Http Basic, OAuth1, OAuth2, and others), Async support, and JSON parsing (thanks to VBA-JSON)
It's working awesomely in Excel 2010 and 2013 (and most likely 2007) and I've got it working with Salesforce, Trello, Basecamp, Google Maps, and it should work with pretty much any webservice.
FWIW as of the time of posting I've found that the old Web References Toolkit of Excel 2003 still produces working VBA code in Excel 2007/10 (note that there have been some shaky moments with various Windows updates over the last 18 months that has stopped this code working so I wouldn't consider my solution 'reliable').
My horrible hack involves installing Excel 2003, then the Web References Toolkit, then installing Excel 2007 or Excel 2010. I've set up 3 PCs using this hack and all are producing working VBA code to consume asmx web services (I haven't tried connecting with other types of web service but I don't see why they wouldn't work).
The official MS method, using VSTO, is a step too far for some of our clients and this VBA hack has kept them happy.