With the original sentence, you can say either. The pair was sold; the shoes were sold: so the pair of shoes was/were. With your new sentence, we're unlikely to ask where our pair of shoes is: we'd just ask where our shoes are. But if we do use 'pair', it stays singular: this pair is more comfortable than the other one.
The noun pair can be followed by a singular or plural verb. The singular is always used when pair denotes the set taken as a single entity: This pair of shoes is on sale. A plural verb is used when the members are considered as individuals: The pair are working more harmoniously now. After a number other than one, pair itself can be either singular or plural, but the plural is now more common: She bought six pairs (or pair) of stockings. http://www.thefreedictionary.com/pair
For some reason, we - or at least I - tend to talk about the shoes as individual items in that situation:
Where are my running shoes?
They are here.
Maybe because in that situation, we're just thinking of the shoes as separate objects to be located, not a pair of things we put on our feet to help us run. Or maybe it's just one of those "that's the way we say it" things.
Edit: Crossposted with the above. I note that British English often uses the plural for collective nouns (in the situation Thomas cites) wheras American English uses the singular.