>You're also most likely going to pay per word, so if you can figure out a good way to not send them sentences you've already had translated you can save some money.

That's why they build those databases of phrases you were referring to, since they apply discounts on matches against those DBs and on repetitions in your document.

Instead, ask explicitly for a Translation Memory file at the end of the job, so that you can retain your personal piece of database of phrases that was produced during the localization of your file (it's your right to have it and serious companies will hand it without fuss).