How do I prove that the act of removing foreign keys doesn't corrupt existing data?

Implementing this stuff at an app level is a nightmare. You and your team will have to test, double check and retest code which does EXACTLY the same thing that's been done by MySQL (for InnoDB) for MILLIONS of users over a period of YEARS.

Follow the discussion (one of the best threads I've seen on stackoverflow) here. With all due respect to you and your team, does your boss REALLY think that you can write bug-free RI (Referential Integrity) code that has significant functionality in less than 5 years? I certainly don't!

I can't tell you the number of times I've read on other forums (primarily Oracle) where some poor schmuck is crying his eyes out over an app he's inherited where RI was enforced at the app layer. Orphaned records, childless parents, inconsistent data... the list goes on and on... data might as well be Swiss cheese, it's got that many holes! Tell your boss to have a read of this book by database professionals (Oracle experts, some of the best, most readable technical writing I've ever seen). From a review here - an outline of what Jonathan Lewis (a man who wrote a 530 page book on only (get this) the FUNDAMENTALS of the Oracle optimiser.

Chapter 10: Design Disasters, by Jonathan Lewis

More war stories, for fans of Chapter 8! "Now prepare yourself to read all about 'The World's Worst Oracle Project.'" - Jonathan Lewis.

This chapter describes some of the most common mistakes in development Oracle database applications. You'll certainly recognise some of them, because so many people stubbornly cling to certain beliefs. I know I like to bring up several of his points when I get into common arguments like these:
1. We want our application to be "Database Independent."
2. We will check data integrity at the application level instead of taking advantage of Oracle's constraint checking abilities.
3. We want to use sequences for our primary keys.

Take CAREFUL note of point 2! If your boss persists with this madness, then my advice to you is to run fast and run far! You will spend your days in a miserable hellhole of constant firefighting, and never be able to fulfill your potential as a developer or a DBA and you'll learn very little! Just a few thoughts!

To counter the points directly:

Drupal doesn't use them and gets along fine without them, so why should we?

Drupal supports many database layers, perhaps at least one of those does not support FKs and they chose to stick with the lowest common feature set? A great many people do use them, the one data point where people aren't using them is relatively meaningless. I know people who don't wear a seatbelt in cars, but I do as do most others...

They're too inflexible when you need to change data and/or structure.

If you are changing your structure to the point where you need to change FK relationships then anything in your existing design can look inflexible (particularly if the existing design didn't properly match the system you were modelling to start with, which is probably why you are looking to alter the existing structure).

They are deliberately inflexible when changing data. They are designed to not let you change data in such a way that integrity could be compromised, even temporarily. Ask for examples where a foreign key constraint would stop a data modification and for each one we'll be able to explain why that is a good thing and how to work with the constraint to achieve your goal without breaking it (or conversely, we might instead tell you why that particular FK relationship is wrong - but that doesn't make other FKs wrong it just means there was a problem with that part of your model).

He's removed them from existing tables to change things and it's caused data corruption that was only noticeable weeks or months later, on high-traffic/ high activity sites, so he'd rather not use them.

Removing them did not cause corruption. Removing them allowed a bug in some other code to cause corruption over time and it wasn't noticed. If the keys had been in place that process would have raised an error and presumably the problem with it would have therefore been noticed and fixed instead of silently being allowed to break more data until noticed. All removing the constraint does is stop the database enforcing the constraint for future inserts/updates/deletes - it does not affect existing data.

I'm not sure how you'd go about conclusively proving to someone who is sure otherwise that this is the case.

The only proof I can think of is first principals: reasserting what foreign key constraints actually do thereby showing that they would not allow inconsistency to appear, and if there are specific examples of the corruption the person has in mind you could work through trying to create that problem with the keys in place (showing that the key would have caused an error instead of allowing the inconsistency to be created).

More specifically about the immediate effect of removing the constraints: show that dropping them does not alter existing data at all. Create a copy of the database, drop the keys in the copy, and run a full comparison of the data to show that nothing changed as a result of the constraints being lifted.

he's against (confident that he can enforce RI at the application level).

At best that is bad use of development/testing time, at worst it will create a nightmare for later. You are reinventing the wheel, probably inefficiently and potentially with bugs, you have to implement your new wheel everywhere code touches that data in every application now and going forward instead of simply letting the database handle it each time, and if one of those bits of code has a bug the data potentially loses integrity for all applications for all time.

There are of course complex business rules that a DBMS can't enforce for you, so you have to implement them in your BL layer, but for the fundamentals like this let the DB handle it.

An extra one not mentioned but I've heard several times: They are inefficient when we make changes to the parent objects

This is due to most DBMSs not automatically creating an index for each FK, many people assume that they do and are surprised that they don't see the performance metrics that they expect. DBs don't do this as it could be very wasteful when not needed (which is more often then you might expect). If you need an index on the columns of the FK, to make cascading updates/deletes (or just simple join queries in that direction) efficient, create one.

Removing foreign keys does not damage data because you are doing DDL to the indexes.

Once you do that, data integrity (even for existing data) going down the road needs its integrity tested.

EXAMPLE

create table parent
(
    id int not null auto_increment,
    ...
    primary key (id)
);
create table child
(
    id int not null auto_increment,
    fk_id int not null,
    ...
    primary key (id),
    key fk_index (fk_id),
    CONSTRAINT FK FOREIGN KEY (fk_id) REFERENCES parent(id)
);

Let's say you remove the constraint

create table parent
(
    id int not null auto_increment,
    ...
    primary key (id)
);
create table child
(
    id int not null auto_increment,
    fk_id int not null,
    ...
    primary key (id),
    key fk_index (fk_id)
);

After days of operation, you should run the following queries

ORPHANED CHILD RECORDS

select COUNT(A.id) orphans from child A left join parent B
on A.fk_id = B.id where B.id IS NULL;

If you get a nonzero number for orphans, you got orphaned child records. Removing the constraint could be a possible factor.

PARENTS WITHOUT CHILDREN

select COUNT(A.id) childless_parents from parent A left join child B
on A.id = B.fk_id where B.id IS NULL;

If you get a nonzero number for childless_parents, you got parents without children (Sorry, this sounds rather redundant). Removing the constraint could be a possible factor.

EPILOGUE

In a perfect world, referential integrity would be either be an afterthought or taken for granted. Therefore, if you are going to remove foreign key constraints, please wake up, get the sandman out of your eyes, go find all the constraints in your DB, and check them periodically.

In the case of nonzero orphans, you must delete those records or go assign them to parents.