I don't have an Edge 500, but I can't stand arm bands...for me they either restrict blood flow, slide down, or get too tight when the arms swell. I would look into a belt clip, i use one for my ipod touch and it hasn't come off, and doesn't bother me when i run, but not sure if thats the best for sat reception.
Have you looked into the forerunner 405? I have that one and use for both running and cycling. Seems like the main difference in the two is the sport mode and wireless sync on the 405, and the altimeter on the edge 500. If you do more running than cycling i'd lean more to the 405.