Can MySQL handle a DB with about 5 billion records? What if it spans
to about 9 TB? How long will it take to search through all this? What
other information can you provide to me? How does this compare to
Oracle and why? Thanks!

If you are a DBA (Oracle certified Data Base Administrator $60K - $90K
yearly), then I recommend Oracle, since a casino I built utilizes
Akami Gaming servers with about 8 disk RAID per cab, x 6 servers per
site x 3 sites annual support cost $41K and the backups are awful, due
to the write /verify, and GRID is a way to go if you got
$$$$$$$$$$$$$$$, and if you don't then your stuck with windows, but I
have to ask is this painted in the corner scenario from poor software
or poor dbase management.  Who in their right mind pushes a dBase to
the edge of corruption?  MySQL, yank a college MIS /IT /Programmer out
of school into an intership, good experience for them and a savings
for you.
What os , MS, Linux, Unix?  VB, C+/C++ and then software patches, new
upgrades, get ready for the reall questions, if you spend x$s will
this version stay the same and what about integration, cross
platforms, recoveries, (everyone craps on this one), DDOS attacks, can
it support WiFi packetizing.... list goes on!!!
Also consider an AS400 (used on ebay $23K) for your compiling and
runtime of CRM and clean your dbase of old crap, if it has not been
cued in 3 months back it up and purge.  We do this every weekend for
all the casino customers and their spending and cashouts to procure a
tiered promotions based on specific machine and max coin in.  1200+
machines in 10/100 base network at 72,000 multiple function per
second, Oracle stands strong, but at $1.9Million dollars, it should be
the best.

MySQL can handle the 5 billion records (you see www.wikipedia.org ?).
Oracle9i is free for download now, it is a good thing.

The main advantage I see in Oracle9i comparing with MySQL 4.x is the
preformance. That is, it supports Stored Procedure. Stored Procedure
is a small program (some SQL statements) stored in the DB and so you
can run it inside the DB (without connecting with the outside, eg. the
DBA) fastly. (because it is stored in the DB, it run fast!).

Don't forget many man years of development and releases from Oracle.
Their tools (pl/sql,analytical functions, bulk
loading,imports,exports,etc...) are far more advanced than any other
db out there.

Then again, after reading a MySQL high performance book, I would love to convert
one of our large databases over to it because I think it could keep up.

Zenoone , we should talk, I can really help you. I could do that for half ,
and make it ten times faster. 
You should fire anyone who suggests you:
a) Use Windows Servers
b) allow outside network connections to your database servers
c) Use wifi on you database servers
I stop there and focus on the question. Seriously,
you need to contact me.
 
Back to the Question:

5 billion records , no problem, recently did it on MySQL 4.

How Fast , that is a hard one to answer. 
Size of records, table design, and query structure all come into play.

9 TB , yes and much more. 

MySQL has been around for quite some time , so has PostGreSQL.
Both of them built on top of solid code from earlier projects.
If you can need something MySQL or PostgreSQL don't provide,
you need to fix your code.  
 
Oracle is a marketing strategy , it has also become a fat hairy
dog with lots of features no one actually uses.

I use Berkeley DB whenever possible.
It will smoke any of the above mentioned.
It's all about the B-Trees.