BES on the Exchange server is only supported with BES Express and less than 75 users.
I don't remember any particularly large issues with my upgrade, but that was about 5 years ago. I don't think you can go straight to SP4, you have to go from 4.1 SP7 to 5.0.3 then to 5.0.4.
This is the upgrade document for SP3:
http://docs.blackberry.com/en/admin/...001-5.0-US.pdf