For SEO purposes, would it make sense to register with Universal Business Listing and buy a package from them? Or it's just going to be a waste of money?
It's hard to determine whether or not buying a package from Universal Business Listing will (significantly) boost your rankings. I very much doubt it. Do your competitors have a listing? Is it normal in your business to have a listing there? Then you can consider it.
Business listings are old school The thing is: registering for business listings is kind of old school. Back in the early 2000's this would really help. Nowadays Search Engines have advanced so much the importance of a diverse high-quality link profile is very important. If you're depending on this one business listing to get you into the competitive rankings you can forget it. If it's part of a larger strategy you can consider it as an option. In the end it's up to you. I would check out how much traffic this listing could potentially get you.
Please note: Regarding linkbuilding and SEO: before spending any money on links, I'd first try to deplete all the "free" links. Links you get because you offer great content, a great service or something similar.
I would draw your attention to the SEOMoz eye tracking study http://www.seomoz.org/blog/eyetracking-google-serps to indicate the increasing value on search results of local business listings, not to mention the leads they generate on a growing basis on mobile, social and GPS. In many mobile results, users see nothing other than these business listings, so I do not quite understand the response that business listings are "old school" for ranking results. Local search in fact is one of the hottest growing sectors of SEO.
Also, evidence from many studies will indicate the Search Engines have not advanced as far as one might think in the area of business listings, at least as far as accuracy is involved. Every audit we do, and those of our competitors as well, indicates 20%-40% of any business's listings are wrong, incomplete or missing altogether. So managing your business listing data is really a foundational SEO process that needs attention.
Just to add to what appears to be a misconception - UBL is not a Directory, it syndicates business profiles to all relevant search platforms on your behalf. It does not do that phony link-building tactic of manufactured directory-placement that was a thing of the 90s. The value of UBL's syndication is that sites like Google see the same deep profile data accurately consistent across genuine citation sources and ranks the results accordingly. Compare the traffic from business listings to that from advertising, then compare the cost. You will quickly see why SEOs almost universally use a business listing service.
I'd say whether or not UBL is worth it depends on whether or not you target local traffic. As I understand it, it's benefit is by design almost exclusively for local SEO and will not likely give you a noticeable boost in national or worldwide SERPs.
This was initially going to be a comment to Chris Travers' answer, but it's gotten long enough to justify making it its own answer.
Local search is one thing, but the majority of UBL's advertised directories are low quality link farms.
And despite UBL advertising Dun & Bradstreet as one of the publishers they have an "agreement" with, UBL itself has no listing in D&B, and neither are many of their clients, which is pretty odd since most businesses don't have to do anything (except actually exist financially) to automatically get picked up by credit databases like D&B.
This brings me to the next point, any popular local search service, like Google/Yahoo/Bing, or branded services like Blackberry Maps, etc. sources their data from data aggregators, who in turn do data mining from:
So most businesses will automatically show up in these local search services as well as popular business listings.
Even if you change your address, you typically just need to follow the normal address change procedures: update your business registration, file a change of address request at the post office, update your billing addresses, and update your address on your website(s) and business collateral.
The only business directories that won't have your correct info will be the ones that nobody uses because their directory is small and incomplete/inaccurate due to requiring each business to manually add themselves.
So instead of paying for a directory listing service, I'd spend that money on advertising or premium listings on popular local search/business directory services. If you're worried about not being listed in a popular directory, do a search for yourself on it. Chances are, if you're a legitimate business, you're gonna be listed there.
If you're not listed in a particular directory, this is something you can easily correct for free. If you're a new business and find yourself missing from many directories, you could expedite your listing by increasing your exposure: