I never did work up the courage to risk rebooting or crashing my BB by playing various encodings. However, I did some further googling and I found this page:

Comprehensive Blackberry Pearl 8100 Guide - PinStack.com - Blackberry Forums

Look for "Media Guide" some way down the page. There you will find the specification range for MP3 encoding. 16Khz seems to be the minimum sample rate and I do not know what the lowest bits per second rate might be but I have selected 16kbps and that seems to work... sound quality does suffer a great deal though.