GTA Vice City Stories was the first game in the series to include a real life celebrity in game, with singer Phil Collins appearing in promotional material and in a number of missions, along with being featured on the soundtrack.
Contributed by skitsjazz
The multiplayer character Decjuan DeMarco appears to be a reference to the film, Don Juan DeMarco.
Contributed by ClaudX
The multiplayer character "Poop Dawg" is most likely a parody of the rapper Snoop Dogg.
Contributed by ClaudX
There is a chain of businesses in the game called "Electric Boulevard". This is a reference to Eddy Grant's song, "Electric Avenue".
Contributed by ClaudX
There are strings of text in the files showing that Leo Teal was intended to return from GTA: Vice City. He also has five missions mentioned in the game's files.

• CH_LEOT: Leo Teal
• LEO_C01: REMOVED
• LEO_C02: REMOVED
• LEO_C03: REMOVED
• LEO_C04: REMOVED
• LEO_C05: REMOVED
Contributed by ClaudX
Attachment
The Army Fatigues outfit originally had the letters "USMC" on the front. This means that Victor would have joined the Marines, and not the Army.
Contributed by ClaudX
Attachment
An unused Tear Gas weapon can be found in the game's files. Both the weapon's HUD icon and texture remain.
Contributed by ClaudX
Attachment
According to a pre-release screenshot, Ionic Real Estate was called M Pirian Real Estate.
Contributed by ClaudX
Attachment
The in-game restaurant Barzini's is a reference to The Godfather, which features a crime family named the Barzinis.
Contributed by ClaudX
The SP89 is chronologically out of place as the game takes place in 1984, while this variant of the MP5 was not made until 1989. The game's version of it is fully-automatic, while in real life it is semi-automatic. However, it may be illegally custom converted to fully-automatic.
Contributed by Psychospacecow
Attachment
Returning from Grand Theft Auto: Vice City is a literal Easter Egg, hidden behind a wall, accessible by jumping off of the roof of the Vice City News building. The egg is shown as currently being constructed by a miniature crane, as Vice City Stories is a prequel to Vice City and the egg has not been completed yet. The room in which it sits is only accessible in the PlayStation 2 port.
Contributed by ClaudX
Attachment
There is a multiplayer character named T.J. Sucker, who is a part of the VCPD. T.J. Sucker is a parody of the 1980s television cop show T.J Hooker.
Contributed by ClaudX
Attachment
Tommy Vercetti's shirt can be seen in the closet of the Compound Safehouse.
Contributed by ClaudX
Attachment
The game originally included a land mine weapon, but it was ultimately cut. The HUD icon for it can still be found in the game's code.
Contributed by ClaudX
Attachment
The gyro copter "Little Willie" is a reference to the famous gyro copter "Little Nellie" used by Sean Connery's 007 in the film You Only Live Twice.
Contributed by ClaudX
In the mission 'Soldier', Vic salutes Jerry even though he is a sergeant. (Sergeants are not considered officers in the military, and hence are not to be saluted.)
Contributed by ClaudX
Attachment
In the beginning cutscene for the mission 'Caught as an Act', Lance is using a .357 instead of the Equalizer, which is the only available Colt Python in the game.
Contributed by ClaudX
In the mission, Domo Arigato Domestoboto, the code to the safe is 8423. If you look at a telephone's keypad, you'll see that the letters on those keys spell out "VICE".
Contributed by ClaudX
Attachment
The Repo Man's design is likely to be a reference to Repo Man, a 1984 cult film in which the punk protagonist wears a similar outfit during his time as a repo-man.
Contributed by ClaudX
Fingerless gloves appear on the PlayStation 2 version of the Hired Muscle outfit; in the PlayStation Portable version, only a wrist band is seen in regular gameplay, while the gloves are only featured in cutscenes.
Contributed by ClaudX
Attachment
Bryan Forbes originally had a mustache.
Contributed by ClaudX
Attachment
The standard hidden package system, in the form of 99 red balloons scattered around the city, is a reference to Nena's 1980s hit song, "99 Luftballons".
Contributed by ClaudX
Attachment
The 'Casual' clothes were originally yellow.
Contributed by ClaudX