As a first step I would like to suggest that you start a server side trace to see as to what is happening.

From the perspective of not capturing too much information and also not adding to much overhead to the server please add a filter so that it captures all events and errors only for SPID associated with stored procedure execution.

This will give you some sort of handle to start your troubleshooting with.

The positive thing is that you seem to be able to replicate this problem very easily and that means the solution is not far away. This is really a interesting problem and a great opportunity for learning something new.