Are you sure you didn't receive the gifts already? I would double-check your PC Boxes to make sure first. I've never heard of a glitch where the Delivery Man didn't show up. Also, did you delete the Wonder Cards? If so then the Delivery Guy will disappear. Starting a New Game won't fix it either. It will just get rid of everything and start a new game. I'm not sure if mixing records would do anything either.
Since you're using a retail cartridge you can use your Action Replay to get the wonder cards onto your game and get the events. In order to do this though you'll need a save editing program that can export a code to plug into your AR and then you can just use the code to get the events.