Late to answer this but here it is:
A) Turned out to be an issue with Android 2.2's bugged SSL implementation. My images are accessible through both HTTPS and HTTP. I was using the HTTPS URL's and the request were failing. I simply switched over to the HTTP URL's and everything started working fine in 2.2
B) I was never able to exactly know if this was really the case, if there was a bug in Picasso's debug mode or what. Upon testing more, I did notice that the app's cache storage did increase over time (i.e. as more images had been accessed more frequently) which would indicate that there was caching involved. However, I think it could be cached HTTP responses instead of cached image files which would explain why Picasso's debug mode indicated they were being requested from the source yet still appeared quickly as if cached.