BES 5.0 works with 2000, 2003 and 2007 SErver
dont know, if you can upgrade to 4.1.x, and, if that would be less expensive then an upgrade to 5.0
But, if you plan to use blackberry for the next years, I think it is safer to upgrade now to 5.0 then now to 4.1 and later to 5.0
BPS would be a step back from full BES, and, is not maintained/actively developed by RIM.
compare 4.1 and 5:
BlackBerry - Enterprise Server Compare - Microsoft Exchange - IBM Lotus Domino
regarding your problem, that looks more like a software problem with the device OS then with the BES - but this is only a guess.