I think exercising and stretching muscles would help. Just get a small barbell or bottle of water and use it to help stretch your shoulder muscles (raise it and lower the weight behind your neck, then raise it again, rinse & repeat) or shoulder rolls. They sound painful, but might be worth it if you can get back rubs out of them.
