The Flickr API imposes a rough limit of 1 query per second on developers. Obviously this is spread over a week, or even a month, so quick bursts are allowed.
I've tried calling PhotosGetSizes 50 times and it seems to take me about 10 seconds, so I'm surprised its taking you so long.
I've also just checked in a new change which allows you to request the image urls along with the search results:
PhotoSearchOptions o = new PhotoSearchOptions();
o.Extras = PhotoSearchExtras.AllUrls;
o.PerPage = 50;
o.Tags = "test";
PhotoCollection photos = f.PhotosSearch(o);
foreach(Photo p in photos)
if( p.DoesLargeExist )
Console.WriteLine("Large image doesn't exist.");
if( p.DoesMediumExist )
Console.WriteLine("Medium image doesn't exist.");