Hi Ryan,
After reading your post and thinking a bit more about this, I don't think Extract by Mask is all that viable. It would require you to summarize each raster created from selected polylines which is just more work. This a.m. I ran Zonal Statistics as Table with many polylines (for the zone features) and it worked really well. The only thing is that it doesn't extract the underlying raster values to form a new raster like the extraction tools do. It will however, provide you with some meaningful statistics about the underlying pixels. Count, Min, Max, Range, Mean, etc... All you have to do is join the output table back to your original polylines using the same field you specified in the Zone Field parameter of the tool. Let me know if this works better for you.
Also, do you polylines cross each other? This will be problematic unless managed properly. What version are you using?
Regards,
Eric