What version of Exchange? What Service pack?
If this is happening sporadically, the destination for the 'stuck' mail may simply be unavailable -- in other words, it's their problem, not yours. Look at the details of the message in the queue. Problems like 'host unavailable' or 'network error during host resolution' are usually at the other end, as long as most of your mail is going through.
If all your outbound mail is extrememly slow, I'd make sure that DNS is configured correctly. There are a lot of other possibilities as well, but I'd need config information before proceeding. Some problem similar to this were fixed with service packs.