The only way to breed a Beldum is to breed it with a Ditto. If the Daycare Man says "The two don't really seem to like each other very much," It's only because they're different species and have the same original trainer, which means you have only a 20% chance of getting an egg (or a 40% with the Oval Charm), so you've just seem to be unlucky. Eventually, you'll get that Beldum egg though.