[|||||||]

That is seriously messed up. If the Handheld has uppercase EDGE and it can send a PIN message then it should work. If the email has worked in the past it is highly unlikely that it is on the network side.

However I can't think of a reason why this would only affect the 8100s.

Your questions:
1)BIS and BES work fine together
2)No you can be provisioned for BIS and not for BES.
3)Highly unlikely
4)see above
other question) Message flow works like this: your BES sends to the mail to the handheld (based on PIN) over the srp connection. It's very unlikely there is an issue.

I'd suggest looking at the BES to see what else is common with these users.
Also, can you send when you have these issues?