The omni plant gift boxes spawn at anytime, not specifically when travelling. My current sim has more than twenty in her inventory right now. I have no problems returning home after travel, other than the occassional long delay. I keep my sim happy, and wait it out when this happens. She has even maxed skills while taking her extra vacation. How long have you allowed the game to continue after the clock stops at the end of the vacation? Guessing from playing without a running clock, I would say that nearly 24 sim hours is the longest I have waited. But, it could be more.
If your sims are definately not going to return home, I would say that the only option is replay your game from the last, pre-vacation game. I believe, if this is an official dynasty you will need permission to do this.
This is just my take on delayed returns, but, it seems to me that delays occur when you have a sim doing a skill maximisation activity at midnight. The game seems to continue until this activity is completed, then, sometimes, it just does not return home immediately afterwards. The sim gets tired, hungry etc., so you have to attend to their needs. But eventually the game realises that you ought to br home.