Ignoring the slow connection speeds, I'd generally suggest that the more users you have that are external compared to internal, the more benefit and justification there is to go with Exchange that isn't on-premises, since the majority of traffic won't be
local.
In your specific case I really wouldn't want to try having 60+ users trying to connect to their email over an internet connection like that. Even in normal operation you're going to struggle with 40 users on a 512k connection, but add 60+ users connecting
into Exchange and potentially receiving large messages and you could quickly have issues.
Just connecting etc shouldn't be an issue since that doesn't use much bandwidth, but all you need is someone to send a largish message to several of those external users and they'll all be downloading (using your upload) it and hammering your connection.
I'm not familiar with the costs for 365 but that's not your only option, other companies offer hosted exchange and may work out cheaper so be more viable. Additionally they might be able to offer some kind of hybrid setup where your local users are hosted
on a local exchange setup, while the external users are on hosted Exchange.